import java.math.BigInteger;
import java.text.DecimalFormat;
import java.util.*;

/**
 * Creat with IntelliJ IDEA
 * Description:
 * User:WZW
 * Date:2022-03-20
 * Time:21:55
 */
class Solution {

    //3_28
    public class Parenthesis {
        public boolean chkParenthesis(String A, int n) {
            if (A==null || n%2==1)return false;
            Stack<Character> stack = new Stack<>();
            char c = A.charAt(0);
            if (c=='(') stack.push(c);
            else return false;
            int i = 1;
            while (i<A.length()){
                c = A.charAt(i);
                if (c==')' && !stack.isEmpty()){
                    stack.pop();
                }else if (c=='('){
                    stack.push(c);
                }else {
                    return false;
                }
                i++;
            }
            return stack.isEmpty();
        }
    }

    //3_24_2
    public int StrToInt(String str) {
        int num =0;
        int flg = 1;
        int i = str.length()-1;
        for ( ; i >=0 ; i--) {
            char c = str.charAt(i);
            if (i==0 && c=='-'){
                num *= -1;
                break;
            }else if (c=='+'){
                break;
            }
            if (c>='0'&& c<='9'){
                num+=flg*(c-'0');
                flg*=10;
            }else {
                return 0;
            }
        }
        return num;
    }

    //3_22_2
    public int MoreThanHalfNum_Solution(int [] array) {
        Arrays.sort(array);
        int index = array.length>>1;
        return array[index];
    }

    //3_30_1
    public int addAB(int A, int B) {
        if (A==0||B==0){
            return A|B;
        }
        StringBuilder sb = new StringBuilder();
        char[] ca = new char[A];
        char[] cb = new char[B];
        sb.append(ca);
        sb.append(cb);
        return sb.length();
    }


    //3_31 day 10
    public boolean checkWon(int[][] board) {
        for (int i = 0; i < board.length; i++) {
            if (board[i][1] == 1 && board[i][1]==board[i][0] && board[i][0]==board[i][2]){
                return true;
            }
            if (board[1][i] == 1 && board[1][i]==board[0][i] && board[0][i]==board[2][i]) {
                return true;
            }
        }
        if (board[1][1]==1 && board[0][0]==board[1][1] && board[0][0]==board[2][2])return true;
        if (board[1][1]==1 && board[0][2]==board[1][1] && board[1][1]==board[2][0])return true;
        return false;
    }

    //4_1 day11
    public int getLCA(int a, int b) {
        if (a==b)return a;
        if (a>b) return getLCA(a>>1,b);
        else return getLCA(a,b>>1);
    }

    //4_2_1 day 12
    public int binInsert(int n, int m, int j, int i) {
        return n|(m<<j);
    }

    //4_12_2
    public int findMinimum(int n, int[] left, int[] right) {
        int leftNum = 0;
        int rightNum = 0;
        int leftCount = 0;
        int rightCount = 0;
        int leftMin = Integer.MAX_VALUE;
        int rightMin = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (left[i] > 0 && right[i] > 0){
                leftCount += left[i];
                rightCount += right[i];
                if (left[i] < leftMin) leftMin = left[i];
                if (right[i] < rightMin) rightMin = right[i];
            }else {
                if (left[i] != 0){
                    leftNum += left[i];
                }else {
                    rightNum += right[i];
                }
            }
        }
        if (leftCount > rightCount){
            rightNum += rightCount - rightMin + 1;
            return leftNum + rightNum + 1;
        }else {
            leftNum += leftCount - leftMin +1;
            return leftNum + rightNum + 1;
        }
    }

    //相同的数出现的次数超过数组的一半，则对数组排序， 该数一定在数组的中间
    public int getValue(int[] gifts, int n) {
        Arrays.sort(gifts);
        int i = gifts[gifts.length >> 1];
        int count = 0;
        for (int j = 0; j < gifts.length; j++) {
            if (gifts[j] == i){
                count++;
            }
            if (count > gifts.length >> 1) {
                return i;
            }
        }
        return 0;
    }

    //day 24
    public int getVal(int[][] board, int i ,int j){
        if (i == 0 && j==0) return board[i][j];
        if (i == 0) return getVal(board, i, j-1) + board[i][j];
        if (j == 0) return getVal(board, i-1, j) + board[i][j];
        int a = getVal(board,i,j-1);//上一步走的右
        int b = getVal(board,i-1,j);
        return Math.max(a,b)+board[i][j];
    }

    public int getMost(int[][] board) {
        return getVal(board,board.length-1,board[0].length-1);
    }

    //day 26
    public int jumpFloorII(int target) {
        if (target == 1) return target;
        if (target == 2) return 2;
        int[] n = new int[target + 1];
        n[1] = 1;
        n[2] = 2;
        for (int i = 3; i <= target; i++) {
            int sum = 0;
            for (int j = 1; j <= target ; j++) {
                if (j == target) sum += 1;
                sum += n[target - j];
            }
            n[i] = sum;
        }
        return n[target];
    }

    //day 27
    public int Add(int num1,int num2) {
        int a = num1 ^ num2;
        int b = (num1 & num2) << 1;
        int c = a;
        while (b != 0) {
            c = a ^ b;
            b = (a & b) << 1;
            a = c;
        }
        return c;
    }

    //day 29
    public void getSum(int[] a, int depth, ArrayList<Integer> s, int sum) {
        if (depth >= a.length) {
            s.add(sum);
            return;
        }
        sum += a[depth];
        getSum(a,depth+1,s,sum);
        sum -= a[depth];
        getSum(a,depth+1,s,sum);
    }

    public int getFirstUnFormedNum(int[] arr) {
        if (arr == null) return 0;
        ArrayList<Integer> sum = new ArrayList<>();
        boolean[] flg = new boolean[arr.length];
        getSum(arr,0,sum,0);
        if (sum.size() > 1) {
            sum.sort(Comparator.naturalOrder());
            int ans = sum.get(1) + 1;
            for (int i = 2; i < sum.size(); i++) {
                if (ans == sum.get(i)) {
                    ans++;
                }
            }
            return ans;
        }
        return 0;
    }

    //day 46
    public int MoreThanHalfNum_Solution2(int[] array) {
        Arrays.sort(array);
        return array[array.length/2];
    }

    //day 48
    public int[] clockwisePrint(int[][] mat, int n, int m) {
        if (mat == null || n ==0 || m == 0) {
            return null;
        }
        int i = 0;
        int j = 0;
        int k = 0;
        int up = 0;
        int down = n - 1;
        int left = 0;
        int right = m - 1;
        int[] ret = new int[m * n];
        while (k < m * n && i >= up && i <= down && j >= left && j <= right) {
            while (k < m * n && j <= right) {//往右
                ret[k++] = mat[i][j];
                j++;
            }
            j--;
            i++;
            up++;
            while (k < m * n && i <= down) {//往下
                ret[k++] = mat[i][j];
                i++;
            }
            i--;
            j--;
            right--;
            while (k < m * n && j >= left) {//往左
                ret[k++] = mat[i][j];
                j--;
            }
            j++;
            i--;
            down--;
            while (k < m * n && i >= up) {//往上
                ret[k++] = mat[i][j];
                i--;
            }
            i++;
            j++;
            left++;
        }
        return ret;
    }

    public int findMax(int[] a, int s, int e) {
        int max = a[s];
        for (int i = s + 1; i <= e; i++) {
            if (a[i] > max) {
                max = a[i];
            }
        }
        return max;
    }

    public int findMaxGap(int[] A, int n) {
        if (A == null || n <= 1) {
            return 0;
        }
        int gap = 0;
        for (int i = 0; i < n - 1; i++) {
            int a = Math.abs(findMax(A,0,i) - findMax(A,i+1,n - 1));
            if (a > gap) {
                gap = a;
            }
        }
        return gap;
    }
}
//有理数运算
class Rational{

    public long numerator;
    public long denominator;
    public long integer;
    public long totalNumerator;
    public boolean isNegtive = false;
    public boolean isZero = false;
    public boolean Nan = false;

    public static long parseNumerator(String s) {
        return Long.parseLong(s.substring(0,s.indexOf('/')));
    }

    public static long parseDenominator(String s) {
        return Long.parseLong(s.substring(s.indexOf('/')+1,s.length()));
    }

    public Rational(long n, long d) {
        if (n == 0) {//分子为0
            isZero = true;
        }
        if (d == 0) {//分母为0
            Nan = true;
            return;
        }
        //符号
        if (n < 0) {
            isNegtive = !isNegtive;//这个学到了！！！！
        }
        if (d < 0) {
            isNegtive = !isNegtive;
        }
        //假分数
        integer = n / d;
        numerator = n - integer * d;
        denominator = d;
        //最简形式
        if (numerator > 1 || numerator < -1) {
            long gcd = calGcd(Math.abs(numerator),Math.abs(denominator));
            if (gcd > 0) {
                numerator /= gcd;
                denominator /= gcd;
            }
        }
        totalNumerator = numerator + integer * denominator;
    }

    private long calGcd(long a, long b) {//求最大公约数
        if (b == 0) return a;
        return calGcd(b,a % b);
    }

    public Rational add(Rational r) {
        long d = denominator * r.denominator;
        long n = totalNumerator * r.denominator + r.totalNumerator * denominator;
        return new Rational(n,d);
    }

    public Rational sub(Rational r) {
        long d = denominator * r.denominator;
        long n = totalNumerator * r.denominator - r.totalNumerator * denominator;
        return new Rational(n,d);
    }

    public Rational mul(Rational r) {
        long d = denominator * r.denominator;
        long n = totalNumerator * r.totalNumerator;
        return new Rational(n,d);
    }

    public Rational div(Rational r) {
        long d = denominator * r.totalNumerator;
        long n = totalNumerator * r.denominator;
        return new Rational(n,d);
    }

    @Override
    public String toString() {
        if (Nan) {//分母有0
            return "Inf";
        }
        if (isZero) {//结果为0
            return "0";
        }
        StringBuffer s = new StringBuffer();
        if (isNegtive) {//结果为负数
            s.append("(-");
        }
        if (integer != 0) {
            s.append(Math.abs(integer));
            if (0 != numerator) {
                s.append(' ');
            }
        }
        if (0 != numerator) {
            s.append(Math.abs(numerator));
            s.append('/');
            s.append(Math.abs(denominator));
        }
        if (isNegtive) {
            s.append(')');
        }
        return s.toString();
    }

}

class subTree {
    String pre;
    String post;
    subTree(String pre, String post) {
        this.pre = pre;
        this.post = post;
    }
}

class staff implements Comparable<staff>{
    int weight;
    int height;

    public staff(int weight, int height) {
        this.weight = weight;
        this.height = height;
    }

    @Override
    public int compareTo(staff o) {
        if (weight == o.weight) {
            return o.height - height;
        }
        return weight - o.weight;
    }
}

public class Test {

    public static void main0(String[] args) {
        Solution s = new Solution();
        int[][] a = {{2,7,3,1,1}};
        int[] b = {1,2,3,4};
        int[][] d = {
                {57,50,59,18,31,13},
                {67,86,93,86,4,9},
                {38,98,83,56,82,90},
                {66,50,67,11,7,69},
                {20,58,55,24,66,10},
                {43,26,65,0,64,28},
                {62,86,38,19,37,98}};
        int[][] c = {{4,46,89},{28,66,99},{26,21,71}};
//        System.out.println(s.getMost(c));
        b = s.clockwisePrint(d,7,6);
        System.out.println();
    }

    //day 47
    //马戏团
    //本质：求最长升序子序列的长度
    //
    public static void main_5_27_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int m = in.nextInt();
            staff[] staffs = new staff[m];
            for (int i = 0; i < m; i++) {
                long n = in.nextInt();
                int w = in.nextInt();
                int h = in.nextInt();
                staffs[i] = new staff(w,h);
            }
            Arrays.sort(staffs);
            //动态规划 最长上升子序列的长度
            int max = 0;
            int[] len = new int[m];
            for (int i = 0; i < m; i++) {
                len[i] = 1;
            }
            for (int i = 1; i < m; i++) {
                for (int j = 0; j < i; j++) {
                    //以第i个元素结尾的最长上升子序列的长度（须包含第i个元素）
                    if (staffs[i].height >= staffs[j].height) {
                        len[i] = Math.max(len[i],len[j] + 1);
                    }
                }
                if (max < len[i]) {
                    max = len[i];
                }
            }
            System.out.println(max);
        }
    }

    //错误：没有认识到height不是有序的，不能直接计算
    public static void main472(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            long m = in.nextInt();
            PriorityQueue<staff> queue = new PriorityQueue<>();
            for (int i = 0; i < m; i++) {
                long n = in.nextInt();
                int w = in.nextInt();
                int h = in.nextInt();
                staff s = new staff(w,h);
                queue.offer(s);
            }
            staff a = queue.poll();
            long cnt = 1;
            while (!queue.isEmpty()) {
                staff b = queue.poll();
                if (a.weight < b.weight && a.height <= b.height) {
                    cnt++;
                    a = b;
                }else if (a.weight == b.weight && a.height == b.height) {
                    cnt++;
                    a = b;
                }
            }
            System.out.println(cnt);
        }
    }

    public static void main5_27_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            long m = in.nextInt();
            PriorityQueue<staff> queue = new PriorityQueue<staff>((o1, o2) -> {
                return o2.compareTo(o1);
            });
            for (int i = 0; i < m; i++) {
                long n = in.nextInt();
                int w = in.nextInt();
                int h = in.nextInt();
                staff s = new staff(w,h);
                queue.offer(s);
            }
            staff a = queue.poll();
            long cnt = 1;
            while (!queue.isEmpty()) {
                staff b = queue.poll();
                if (a.weight >= b.weight) {
                    cnt++;
                    a = b;
                }
            }
            System.out.println(cnt);
        }
    }

    //合唱团
    public static void main5_27_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int[] array = new int[n];
            for (int i = 0; i < n; i++) {
                array[i] = in.nextInt();
            }
            int k = in.nextInt();
            int d = in.nextInt();
        }
    }

    //day 46 通过
    public static void main5_26_2(String[] args) {
        Scanner in = new Scanner(System.in);
        List<String> list = new ArrayList<>();
        while (in.hasNextLine()) {
            String s = in.nextLine();
            if (s .equals("")) {//输入结束
                break;
            }
            //处理string
            if (s.contains("\\")) {
                int index = s.lastIndexOf('\\');
                s = s.substring(index + 1);
            }
            list.add(s);//用list保存错误名称和行数
        }
        int[] table = new int[list.size()];//用于记录strings中对应字符串的数量
        List<String> strings = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            String[] ss = list.get(i).split(" ");
            if (ss[0].length() > 16) {//只取最后16位
                int id = ss[0].length() - 16;
                ss[0] = ss[0].substring(id);
            }
            String sss = ss[0] + " " + ss[1];//重新将行号进行拼接
            //sss进行去重 并计数
            if (strings.contains(sss)) {
                int j = strings.indexOf(sss);
                table[j]++;
            } else {
                strings.add(sss);
                table[strings.indexOf(sss)] = 1;
            }
        }
        int start = strings.size() - 8 <= 0 ? 0 : strings.size() - 8;//总数可能不满8个
        for (int i = start; i < strings.size(); i++) {
            System.out.println(strings.get(i) + " " + table[i]);
        }
    }

    //day 45 通过
    public static boolean isBro(String a, String b) {
        if (a.equals(b) || a.length() != b.length()) {
            return false;
        }
        int[] list = new int['z'-'a' + 1];
        for (int i = 0; i < a.length(); i++) {
            list[a.charAt(i) - 'a']++;
        }
        for (int i = 0; i < b.length(); i++) {
            list[b.charAt(i) - 'a']--;
            if (list[b.charAt(i) - 'a'] < 0) {
                return false;
            }
        }
//        for (int i = 0; i < a.length(); i++) {
//            if (list[a.charAt(i) - 'A'] != 0) {
//                return false;
//            }
//        }
        return true;
    }

    public static List<String> getBro(String s, String[] w) {
        List<String> ans = new ArrayList<>();
        for (int i = 0; i < w.length; i++) {
            if (isBro(s,w[i])){
                ans.add(w[i]);
            }
        }
        return ans;
    }

    public static void main5_25_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            String[] words = new String[n];
            for (int i = 0; i < n; i++) {
                words[i] = in.next();
            }
            String s = in.next();
            int k = in.nextInt();
            List<String> list = getBro(s,words);
            list.sort(Comparator.naturalOrder());
            System.out.println(list.size());
            if (k <= list.size()) {
                System.out.println(list.get(k - 1));
            }
        }
    }

    public static boolean isContain(String a, String b) {
        if (a.equals(b) || a.contains(b)) {
            return true;
        }
        int[] list = new int['Z'-'A' + 1];
        for (int i = 0; i < a.length(); i++) {
            list[a.charAt(i) - 'A']++;
        }
        for (int i = 0; i < b.length(); i++) {
            list[b.charAt(i) - 'A']--;
            if (list[b.charAt(i) - 'A'] < 0) {
                return false;
            }
        }
        return true;
    }

    public static void main5_25(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String a = in.next();
            String b = in.next();
            if (isContain(a,b)) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }

    //day 44
    public static void main5_25_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String s = in.nextLine();
            String[] strings = s.split("[^(a-z||A-Z)]");
            Stack<String> stack = new Stack<>();
            for (String ss : strings) {
                stack.push(ss);
            }
            while (!stack.isEmpty()) {
                System.out.print(stack.pop());
                if (stack.size()>=1) {
                    System.out.print(" ");
                }
            }
            System.out.println();
        }
    }

    public static void main5_24_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String s = in.nextLine();
            StringBuffer stringBuffer = new StringBuffer();
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i)=='_') {
                    i++;
                    stringBuffer.append(Character.toUpperCase(s.charAt(i)));
                } else {
                    stringBuffer.append(s.charAt(i));
                }
            }
            System.out.println(stringBuffer.toString());
        }
    }

    //day 43
    public static void main5_23_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            String[] t = new String[]{"2ABC","3DEF","4GHI","5JKL","6MNO","7PQRS","8TUV","9WXYZ"};
            int n = in.nextInt();
            String[] strings = new String[n];
            for (int i = 0; i < n; i++) {
                strings[i] = in.next();
            }
            ArrayList<String> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                char[] c = strings[i].toCharArray();
                StringBuffer stringBuffer = new StringBuffer();
                for (int j = 0; j < c.length; j++) {
                    if (c[j] == '-') {
                        continue;
                    } else if (c[j] <= '9' && c[j] >= '0') {
                        stringBuffer.append(c[j]);
                    } else {
                        for (int k = 0; k < t.length; k++) {
                            if (t[k].contains(c[j]+"")) {
                                stringBuffer.append(t[k].charAt(0));
                            }
                        }
                    }
                }
                stringBuffer.insert(3,'-');
                if (!list.contains(stringBuffer.toString())) {
                    list.add(stringBuffer.toString());
                }
            }
            list.sort(Comparator.naturalOrder());
            for (String s : list) {
                System.out.println(s);
            }
            System.out.println();
        }
    }

    public static int getSum(List<Integer> list) {
        int sum = 0;
        for (int i : list) {
            sum += i;
        }
        return sum;
    }

    public static void dfs(int target, int[] array, List<Integer> path, List<List<Integer>> result, int depth) {
        int sum = getSum(path);
        if (target < sum) {//还没排列完，但是已经大于目标值了，就不用再组合了
            return;
        } else if (target == sum) {//已经等于目标值，不同再组合了
            result.add(new ArrayList<>(path));
            return;
        }
        if (depth >= array.length) {
            return;
        }
        path.add(array[depth]);
        dfs(target,array,path,result,depth+1);
        path.remove(path.size() - 1);
        dfs(target,array,path,result,depth+1);
    }
//
    public static void main5_23_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int m = in.nextInt();
            n  = n <= m ? n : m;//＞m的部分不符合，直接淘汰
            int[] array = new int[n];
            for (int i = 1; i <= n; i++) {//初始化数组
                array[i-1] = i;
            }
            List<Integer> list = new ArrayList<>();
            List<List<Integer>> result = new ArrayList<>();
            dfs(m,array,list,result,0);
            for (List<Integer> l : result) {
                for (int i = 0; i < l.size(); i++) {
                    if (i > 0) {
                        System.out.print(" ");
                    }
                    System.out.print(l.get(i));
                }
                System.out.println();
            }
        }
    }

    //day 42
    //走迷宫
    //bfs 广度优先遍历 类似二叉树深度

    //bfs 还不太懂，听老师讲解
    public static int[][] dir = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};

    public static void main_5_21_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            char[][] table = new char[10][10];
            boolean[][] flag = new boolean[10][10];
            for (int i = 0; i < 10; i++) {
                for (int j = 0; j < 10; j++) {
                    flag[i][j] = false;
                }
            }
            for (int i = 0; i < 10; i++) {
                table[i] = in.nextLine().toCharArray();
            }
            Queue<int[]> queue = new LinkedList<>();
            queue.offer(new int[] {0,1});
            int cnt = -1;
            boolean flg = false;
            while (!queue.isEmpty() && !flg) {
                int size = queue.size();
                cnt++;
                while (size-- > 0) {
                    int[] index = queue.poll();
                    if (index[0] == 9 && index[1] == 8) {
                        flg = true;
                        break;
                    }
                    for (int i = 0; i < 4; i++) {
                        int[] nindex = new int[2];
                        nindex[0] = index[0] + dir[i][0];
                        nindex[1] = index[1] + dir[i][1];
                        if (nindex[0] <= 0 || nindex[0] > 9 || nindex[1] <= 0 || nindex[1] > 9 || flag[nindex[0]][nindex[1]] == true || table[nindex[0]][nindex[1]] == '#') {
                            continue;
                        }
                        queue.offer(nindex);
                        flag[nindex[0]][nindex[1]] = true;
                    }
                }
            }
            System.out.println(cnt);
        }
    }

    public static void main5_21_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            char[][] table = new char[10][10];
            int[][] step = new int[10][10];
            //初始化
            for (int i = 0; i < 10; i++) {
                for (int j = 0; j < 10; j++) {
                    step[i][j] = 0;
                }
            }
            for (int i = 0; i < 10; i++) {
                table[i] = in.nextLine().toCharArray();
            }
            int direction = 1;
            step[1][1] = 1;
            int i = 1;
            int j = 1;
            while (i >= 0 && i <= 9 && j >= 0 && j <= 9) {
                if (direction == 1) {//从上面走
                    if (table[i][j] != '#') {
                        step[i][j] = step[i-1][j] + 1;
                        i++;//继续往下
                    } else {//回到上一步
                        i--;
                        if (table[i][j+1] !='#') {//向右
                            direction = 2;
                            j++;
                        } else if (table[i][j-1] != '#') {//向左
                            direction = 3;
                            j--;
                        }
                    }
                } else if (direction == 2) {//从左边走
                    if (table[i][j] != '#') {
                        step[i][j] = step[i][j-1] + 1;
                        j++;
                    } else {//回到上一步
                        j--;
                        if (table[i+1][j] !='#') {//向下
                            direction = 1;
                            i++;
                        } else if (table[i-1][j] != '#') {//向上
                            direction = 4;
                            i--;
                        }
                    }
                } else if (direction == 3) {//从右边走
                    if (table[i][j] != '#') {
                        step[i][j] = step[i][j+1] + 1;
                        j--;
                    } else {//回到上一步
                        j++;
                        if (table[i+1][j] !='#') {//向下
                            direction = 1;
                            i++;
                        } else if (table[i-1][j] != '#') {//向上
                            direction = 4;
                            i--;
                        }
                    }
                } else {//从下边走
                    if (table[i][j] != '#') {
                        step[i][j] = step[i+1][j] + 1;
                        i--;
                    } else {//回到上一步
                        i++;
                        if (table[i][j+1] !='#') {//向右
                            direction = 2;
                            j++;
                        } else if (table[i][j-1] != '#') {//向左
                            direction = 3;
                            j--;
                        }
                    }
                }
            }
            System.out.println(step[8][8]+1);
        }
    }

    public static void main5_21_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String s = in.nextLine();
            StringBuilder stringBuilder = new StringBuilder();
            for (char c:s.toCharArray()) {
                if (c >= '0' && c <= '9') {
                    stringBuilder.append(c);
                }
            }
            System.out.println(stringBuilder.toString());
        }
    }

    //day 41
    //五子棋
    //深度优先遍历
    //计数起点 不为空
    //四个方向统计棋子数(给个方向又分为两个方向 统计超过5子返回)
    public static int[][][] direction = new int[][][] {
            {{0,-1},{0,1}},//横向  向左 向右
            {{-1,0},{1,0}},//竖向  向上 向下
            {{-1,1},{1,-1}},// /   右上 左下
            {{-1,-1},{1,1}},// \   左上 右下
    };

    public static int count(String[] t, int x , int y, char ch) {
        int result = 0;
        for (int i = 0; i < direction.length; i++) {
            int cnt = 0;
            for (int j = 0; j < direction[0].length; j++) {
                int nx = x;
                int ny = y;
                while (nx >= 0 && nx < t.length && ny >= 0 && ny < t[0].length() && ch == t[nx].charAt(ny)) {
                    cnt++;
                    nx += direction[i][j][0];
                    ny += direction[i][j][1];
                }
            }
            result = result < cnt ? cnt : result;
        }
        return result - 1;
    }

    public static boolean solve(String[] table) {
        for (int i = 0; i < table.length; i++) {
            for (int j = 0; j < table[0].length(); j++) {
                //遍历找到有落子的位置，开始判断是否有五子连珠
                if (table[i].charAt(j) != '.') {
                    if (count(table, i, j , table[i].charAt(j)) >= 5) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    public static void main_5_20_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String[] table = new String[20];
            for (int i = 0; i < 20; i++) {
                table[i] = in.nextLine();
            }
            System.out.println(solve(table) ? "Yes" : "No");
        }
    }

    public static boolean hasWinner(String[] t, int i, int j) {
        char c = t[i].charAt(j);
        int count = 1;
        //竖
        if (i <= 15) {
            for (int k = i + 1; k < i+5; k++) {
                if (t[k].charAt(j) == c) {
                    count++;
                } else {
                    count = 1;
                    break;
                }
            }
        }
        if (count >= 5) {
            return true;
        }
        //左斜
        if (j >= 4 && i <= 15) {
            for (int k = i + 1, l = j - 1; k < i+5; k++, l--) {
                if (t[k].charAt(l) == c) {
                    count++;
                } else {
                    count = 1;
                    break;
                }
            }
        }
        if (count >= 5) {
            return true;
        }
        if (j <= 15 && i <= 15) {
            for (int k = i + 1, l = j + 1; k < i+5; k++, l++) {
                if (t[k].charAt(l) == c) {
                    count++;
                } else {
                    count = 1;
                    break;
                }
            }
        }
        return count >= 5;
    }

    public static void main5_20_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String[] t = new String[20];
            boolean flg = false;
            int[][] index = new int[20][20];
            for (int i = 0; i < 20; i++) {
                for (int j = 0; j < 20; j++) {
                    index[i][j] = -1;
                }
            }
            for (int i = 0; i < 20; i++) {
                t[i] = in.nextLine();
                if (t[i].contains("+++++") || t[i].contains("*****")) {
                    flg = true;
                    break;
                }
                if (t[i].contains("+") || t[i].contains("*")) {
                    int k = 0;
                    for (int j = 0; j < 20; j++) {
                        if (t[i].charAt(j) != '.') {
                            index[i][k] = j;
                            k++;
                        }
                    }
                }
            }
            for (int i = 0; i < 20; i++) {
                if (index[i][0] == -1 ) {
                    continue;
                }
                for (int j = 0; j < 20; j++) {
                    if (index[i][j] == -1) {
                        break;
                    }
                    if (hasWinner(t,i,index[i][j]) == true) {
                        flg = true;
                    }
                }
            }
            if (flg) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }

    public static void main5_20_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int a = in.nextInt();
            String ss = "+-*/";
            Stack<Integer> stack = new Stack<>();
            for (int i = 0; i < a; i++) {
                String s = in.next();
                if (ss.contains(s) && stack.size() >= 2) {
                    int m = stack.pop();
                    int n = stack.pop();
                    if (ss.indexOf(s) == 0) {
                        stack.push(m + n);
                    } else if (ss.indexOf(s) == 1) {
                        stack.push(n - m);
                    } else if (ss.indexOf(s) == 2) {
                        stack.push(m * n);
                    } else {
                        stack.push(n / m);
                    }
                } else {
                    stack.push(Integer.valueOf(s));
                }
            }
            if (!stack.isEmpty()) {
                System.out.println(stack.peek());
            }
        }
    }

    //day 40
    //问题：最长上升子序列
    //子问题：以i结尾的最长上升子序列
    //初始状态：f(0) = 1;
    //状态转移：f(i) = Max(f(i-1), f(i-n)) + 1  ---> Math(f(i),f(i-n)+1) 先用f(i)来保存前面的数+1中的最大值！！

//    public static int countLongest(int[] array, int n) {
//        if (n <= 1) return n;
//        int[] num = new int[n];
//        num[0] = 1;
//        for (int i = 1; i < n; i++) {
//            if (array[i] > array[i-1]) {
//                int m = num[i-1];
//                for (int j = i-2; j >= 0; j--) {
//                    if (num[j] > m && array[j] < array[i]){
//                        m = num[j];
//                    }
//                }
//                num[i] = m + 1;
//            } else {
//                int k = i - 2;
//                while (k > 0 && array[i] <= array[k]) {
//                    k--;
//                }
//                if (k <= 0) {
//                    num[i] = array[i] > array[0] ? 2 : 1;
//                } else {
//                    int m = num[k];
//                    for (int j = k - 1; j >= 0; j--) {
//                        if (num[j] > m && array[j] < array[i]){
//                            m = num[j];
//                        }
//                    }
//                    num[i] = m + 1;
//                }
//            }
//        }
//        int max = num[0];
//        for (int i = 1; i < n; i++) {
//            if (num[i] > num[0]) {
//                max = num[i];
//            }
//        }
//        return max;
//    }

    //动态规划
    public static int countLongest(int[] array, int n) {
        if (n <= 1) return n;
        int[] num = new int[n];
        num[0] = 1;
        int max = 1;
        for (int i = 1; i < n; i++) {
            num[i] = 1;
            for (int j = i - 1; j >= 0 ; j--) {
                if (array[i] > array[j]) {
                    num[i] = Math.max(num[i],num[j] + 1);//?? !! 第一次遇到比array[i]小的数的时候，num[j]+1可能比更前面的array[j]+1小
                }
            }
            if (max < num[i]) {
                max = num[i];
            }
        }
        return max;
    }

    public static void main5_19_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int a = in.nextInt();
            int[] array = new int[a];
            for (int i = 0; i < a; i++) {
                array[i] = in.nextInt();
            }
            System.out.println(countLongest(array, a));
        }
    }


    //要改成long类型才能过
    public static long count(int n) {
        if (n <= 1) return 0;
        if (n == 2) return 1;
        return (n-1) * (count(n-1) + count(n-2));//要找到这个规律，其实我想到了，但是没有从递归来实现，信心已经被打击完了……
    }


    public static void main5_19_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int a = in.nextInt();
            System.out.println(count(a));
        }
    }

    //day 39
    //转化成26进制 类似数字的十进制
    //当长度不超过字符串的长度时，直接按照16进制进行加减
    //当长度超过字符串的长度时，先补位，s1补'a',s2补'z+1'，进行加减的时候，其实就是前面的位相减之后，权重增加，最后+0*26^0。
    public static long count(String s1, String s2, int a, int b) {
        StringBuffer stringBuffer1 = new StringBuffer(s1);
        StringBuffer stringBuffer2 = new StringBuffer(s2);
        for (int i = s1.length(); i < b; i++) {
            stringBuffer1.append('a');
        }
        for (int i = s2.length(); i < b; i++) {
            stringBuffer2.append('z'+1);
        }
        int[] array = new int[b];
        for (int i = 0; i < b; i++) {
            array[i] = stringBuffer2.charAt(i) - stringBuffer1.charAt(i);
        }
        int ret = 0;
        for (int i = a; i <= b; i++) {
            for (int j = 0; j < i; j++) {
                ret += array[j] * Math.pow(26,i - j - 1);
            }
        }
        return ret - 1;
    }
    public static long count1(String s1, String s2, int a, int b) {
        long num = 1;
        char[] cap = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
        String c = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
        for (int j = a; j <= b; j++) {
            int indexa = 0;
            int indexb = 0;
            if (j >= s1.length() && j >= s2.length()) {
                indexa = 0;
                indexb = c.length()-1;
            } else if (j >= s1.length()) {
                indexa = 0;
                indexb = c.indexOf(s2.charAt(j));
            } else if (j >= s2.length()) {
                indexa = c.indexOf(s1.charAt(j));
                indexb = c.length()-1;
            } else {
                indexa = c.indexOf(s1.charAt(j));
                indexb = c.indexOf(s2.charAt(j));
            }
            int k = indexb - indexa;
            num += (num * k) % 1000007;
        }
        return num;
    }
    //
    public static void main5_18_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String s1 = in.next();
            String s2 = in.next();
            int a = in.nextInt();
            int b = in.nextInt();
            System.out.println(count(s1, s2, a, b) % 1000007);
        }
    }


    //最长公共子序列 动态规划
    //问题：字符串s1长度为m,字符串s2长度为n，求其最长公共子序列
    //状态：f(i,j)字符串s1中以i结尾的字符串和s2中以j结尾的字符串的最长公共子序列的长度
    //状态转移：f(i,j)= s1[i]==s2[j] ? f(i-1,j-1)+1 : max(f(i-1,j),f(i,(j-1))
    public static int common(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        //动态规划 二维数组初始化
        int[][] dp = new int[m+1][n+1];
        for (int i = 0; i < m + 1; i++) {
            dp[i][0] = 0;
        }
        for (int i = 0; i < n + 1; i++) {
            dp[0][i] = 0;
        }
        for (int i = 1; i < m+1; i++) {
            for (int j = 1; j < n+1; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }

    public static int common(String s1, String s2, int a) {
        int max = 0;
        int count = 0;
        if (s1 == null || s2 == null) return max;
        if (s1.length() < s2.length()) return common(s2,s1);//保证1是更长的串
        if (s1.contains(s2)) return s2.length();
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        for (int i = 0; i < s2.length(); i++) {
            int l = i;
            count = 0;
            int j = s1.indexOf(str2[i]);
            if (j == -1) continue;
            for (; j < s1.length(); j++) {
                int k = j;
                for (; k < s2.length(); k++) {
                    if (l < str2.length && str2[l] == str1[k]) {
                        count++;
                        l++;
                    }
                }
                if (max < count) {
                    max = count;
                }
            }
        }
        return max;
    }

    public static void main5_18_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String s1 = in.next();
            String s2 = in.next();
            System.out.println(common(s1, s2));
        }
    }

    //day 38
    //红与黑
    //算法：深度优先遍历 图 选择任意一条没有走过的路，一直走下去，直到无路可走
    //     然后记录结果，返回上一步，选择其他没有走过的路，直到最开始的位置的路都走完（递归）
    //     涉及到返回，因此需要标记走过的路
    //思路：
    //1. 输入， 找到标记位置
    //2. 用一个数组标记四个方向
    //3. 选择一条没有走过的路走，走到没有路走就返回，或者碰到不能走的砖块(递归)
    //4. 走到1个，计数器+1
    public static int[][] drection = new int[][]{{-1,0},{0,-1},{1,0},{0,1}};//上、左、下、右
    public static boolean[][] flg;

    public static int count(char[][] map, int m, int n, int x, int y, boolean[][] flg) {
        int ret = 0;
        if (x < m && y < n && x >= 0 && y >= 0 && !flg[x][y]) {
            flg[x][y] = true;
            if (map[x][y] == '.' || map[x][y] == '@') {//只有这两种情况，才需要记录并向另外四个方向走
                ret++;
                for (int i = 0; i < 4; i++) {
                    //这里需要另外定义变量，以防止破坏了x和y的值
                    int j = x + drection[i][0];
                    int k = y + drection[i][1];
                    ret += count(map,m,n,j,k,flg);
                }
            }
        }
        return ret;
    }

    //
    public static void main_5_18(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int m = sc.nextInt();
            int n = sc.nextInt();
            String ss = sc.nextLine();
            int x = 0;
            int y = 0;//标记起始位置
            char[][] map = new char[m][n];
            //输入地图
            for (int i = 0; i < m; i++) {
                String s = sc.nextLine();
                map[i] = s.toCharArray();
                if (s.contains("@")) {
                    //找到起始位置
                    x = i;
                    y = s.indexOf('@');
                }
            }
            flg = new boolean[m][n];
            System.out.println(count(map, m, n, x, y, flg));
        }
    }

    public static void main5_18(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        Boolean[][] color = new Boolean[m][n];
        int[][] path = new int[m][n];
        int max = 1;
        int[] index = new int[2];
        String c;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
               c = sc.next();
               if (c.equals(".")) {
                   color[i][j] = true;
               } else if (c.equals("@")) {
                   index[0] = i;
                   index[1] = j;
               }
            }
        }
        int i = index[0];
        int j = index[1];
        while (i >= 0 && i < m && j >= 0 && j < n) {
            //边界
            if (i == 0 || i == m - 1) {
                if (j == 0 || j == n - 1) {
                    if (color[i][j] == true) {

                    }
                }
            }
        }
    }

    public static void countP(Boolean[][] t,int n, int m, int x, int y,int[] val) {
        if (x >= n && y >= m) {
            return;
        }
        if (t[x][y] == true) {
            val[0]++;
        }
        if (x == n) {
            //只能向右走
            countP(t,n,m,x,y+1,val);
        } else if (y == m) {
            //只能向下走
            countP(t,n,m,x+1,y,val);
        } else {
            val[1]++;
            countP(t,n,m,x,y+1,val);
            countP(t,n,m,x+1,y,val);
        }
    }

    public static double countP(Boolean[][] t,int n, int m) {
        int[][] dp = new int[n+1][m+1];
        int[][] dp2 = new int[n+1][m+1];
        dp[1][1] = 1;
        for (int i = 2; i <= n; i++) {
            dp2[i][1] = 1;
            if (t[i][1] == false) {
                dp[i][1] = dp[i-1][1];
            }
        }
        for (int j = 2; j <= m; j++) {
            dp2[1][j] = 1;
            if (t[1][j] == false) {
                dp[1][j] = dp[1][j-1];
            }
        }
        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= m; j++) {
                dp2[i][j] = dp2[i][j-1] + dp2[i-1][j];
                if (t[i][j] == false) {
                    dp[i][j] = dp[i][j-1] + dp[i-1][j];
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        return 1.0 * dp[n][m] / dp2[n][m];
    }

    //蘑菇阵
    //看讲解后写 动态规划
    public static double countP(int[][] t,int n, int m) {
        double[][] dp = new double[n+1][m+1];//保存计算结果
        dp[1][1] = 1.0;
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                if (t[i][j] == 1){
                    //碰到蘑菇
                    dp[i][j] = 0.0;
                }else if (!(i == 1 && j == 1)) {
                    //计算概率  下边界（只能往右走）和又边界（只能往下走）(这里第一次写的时候没有搞清楚)
                    dp[i][j] = dp[i-1][j] * (j == m ? 1 : 0.5) + dp[i][j-1] * (i == n ? 1 : 0.5);
                }
            }
        }
        return dp[n][m];
    }

    public static void main_5_17_2(String[] args) {//更正版
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int m = in.nextInt();
            int k = in.nextInt();
            int[][] t = new int[n+1][m+1];
            //初始化矩阵
            for (int i = 0; i < n + 1; i++) {
                for (int j = 0; j < m + 1; j++) {
                    t[i][j] = 0;
                }
            }
            //放入蘑菇
            for (int i = 0; i < k; i++) {
                int x = in.nextInt();
                int y = in.nextInt();
                t[x][y] = 1;
            }
            double ans = countP(t,n,m);
            System.out.printf("%.2f\n",ans);
        }
    }

    public static void main5_17_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int m = in.nextInt();
            int k = in.nextInt();
            Boolean[][] t = new Boolean[n+1][m+1];
            for (int i = 0; i < n + 1; i++) {
                for (int j = 0; j < m + 1; j++) {
                    t[i][j] = false;
                }
            }
            for (int i = 0; i < k; i++) {
                int x = in.nextInt();
                int y = in.nextInt();
                t[x][y] = true;
            }
            double ans = countP(t,n,m);
            System.out.printf("%.2f\n",ans);
        }
    }

    //day 37
    //mkdir
    public static void main_5_16_2(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            String strings[] = new String[n];
            for(int i = 0; i < n; i++){
                strings[i] = sc.next();
            }
            Arrays.sort(strings);//排序
            boolean[] flg = new boolean[n];
            for (int i = 1; i < n; i++) {
                if (strings[i].contains(strings[i-1]+"/") && strings[i].indexOf(strings[i - 1]+"/") == 0) {
                    flg[i - 1] = true;
                }
            }
            for (int i = 0; i < n; i++) {
                if (! flg[i]) {
                    System.out.println("mkdir -p " + strings[i]);
                }
            }
            System.out.println();
        }
    }

    public static void main5_16_2(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            String strings[] = new String[n];
            for(int i = 0; i < n; i++){
                strings[i] = sc.next();
                for (int j = 0; j < i; j++) {
                    if (strings[i].contains(strings[j]+"/") && strings[i].indexOf(strings[j]) == 0) {
                        strings[j] = "";
                    }//如果有空？？
                }
            }
            ArrayList<String> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if (!strings[i] .equals("")) {
                    list.add("mkdir -p "+strings[i]);
                }
            }
            list.sort(Comparator.naturalOrder());
            for (int i = 0; i < list.size(); i++) {
                System.out.println(list.get(i));
            }
            System.out.println();
        }
    }

    public static void main5_16_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            String s = in.nextLine();
            int max = 0;
            Stack<Boolean> stack = new Stack<>();
            for (int i = 0; i < n; i++) {
                s = in.nextLine();
                if (s.contains("disconnect")) {
                    stack.pop();
                } else {
                    stack.push(true);
                }
                if (max < stack.size()) {
                    max = stack.size();
                }
            }
            System.out.println(max);
        }
    }

//    class Fraction {
//        long a1, a2, k;
//        boolean flg;
//        public Fraction(long a, long b) {
//            if (a < 0 && b < 0 ) {
//                a = -a;
//                b = -b;
//            }
//            if (a < 0 || b < 0) {//负数
//                flg = true;
//                if (a < 0) {
//                    a = -a;
//                } else {
//                    b = -b;
//                }
//            }
//            k = a / b;
//            a1 = a % b;
//            a2 = b;
//            simplify();
//        }
//        public Fraction(Fraction a) {
//            a1 = a.a1;
//            a2 = a.a2;
//            k = a.k;
//            if (a.flg) {
//                flg = false;
//            } else {
//                flg = true;
//            }
//        }
//
//        public void setFlg(boolean isN) {
//            flg = isN;
//        }
//
//        public void addK(long n) {
//            if (n < 0) {
//                if (flg) {
//                    flg = false;
//                } else {
//                    flg = true;
//                }
//            }
//            k += Math.abs(n);
//        }
//
//        public void simplify() {//化简
//            long a = a1;//分子
//            long b = a2;//分母
//            long c = a % b;
//            while (c != 0) {
//                a = b;
//                b = c;
//                c = a % b;
//            }
//            a1 /= b;
//            a2 /= b;
//        }
//
//        public Fraction add(Fraction b) {
//            long nd = Math.abs(a2) * Math.abs(b.a2);//分母
//            long n1 = a1 * b.a2; //a的分子
//            long n2 = a2 * b.a1;//b的分子
//            if (flg == b.flg) {//两数同号
//                long nn = n1 + n2;
//                Fraction ret = new Fraction(nn,nd);
//                ret.setFlg(flg);
//                ret.addK(k + b.k);
//                return ret;
//            } else {//两数异号
//                if (flg) {
//                    long nn = n2 - n1;
//                    Fraction ret = new Fraction(nn,nd);
//                    ret.addK(b.k - k);
//                    return ret;
//                } else {
//                    long nn = n1 - n2;
//                    Fraction ret = new Fraction(nn,nd);
//                    ret.addK(k - b.k);
//                    return ret;
//                }
//            }
//        }
//
//        public Fraction sub(Fraction b) {
//            Fraction tmp = new Fraction(b);
//            return add(b);
//        }
//
//        public long mul(Fraction b) {
//            long nd = a2 * b.a2;//分母
//            long n = a1 * b.a1;//分子
//            Fraction ret = new Fraction(n,nd);
//
//        }
//    }

    //pre-post

    public static int calPossible(int n, int m) {
        m = (n - m > m) ? m : (n - m);
        int a = factorial(m);//分母
        int b = 1;
        for (int i = 0; i < m; i++) {
            b *= n;
            n--;
        }
        return b / a;
    }

    public static int treePossible(int n, String pre, String post) {
        int rootIndexpre = 1;//前序中子树根的位置
        int firstIndexPost = 0;//后序遍历中子树的起始位置
        ArrayList<subTree> list = new ArrayList<>();//存储子树
        while (rootIndexpre < pre.length()) {//存储子树
            int rootIndexPost = post.indexOf(pre.charAt(rootIndexpre));//下一子树根节点的位置
            int subtreeNodeCount = rootIndexPost-firstIndexPost+1;//子树的节点数
            String subPre = pre.substring(rootIndexpre,rootIndexpre + subtreeNodeCount);
            String subPost = post.substring(firstIndexPost,firstIndexPost+subtreeNodeCount);
            subTree subTree = new subTree(subPre,subPost);
            list.add(subTree);
            rootIndexpre += subtreeNodeCount;//下一个子树根节点的位置
            firstIndexPost = rootIndexPost + 1;
        }
        //计算可能性
        int i = 1;
        i *= calPossible(n,list.size());//组合数n种之中取list.size()种
        for (subTree sub : list) {//递归计算可能性
            i *= treePossible(n,sub.pre,sub.post);//乘以各个子树的可能性
        }
        return i;
    }

    public static void main5_15_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            if (n == 0) {
                break;
            }
            String pre = in.next();
            String post = in.next();
            System.out.println(treePossible(n, pre, post));
        }
    }

    public static BigInteger[] num = new BigInteger[3];

    public static void mul(long a1, long a2, long b1, long b2) {
        BigInteger nd = BigInteger.valueOf(a1 * b1);//分母
        BigInteger nn = BigInteger.valueOf(a2 * b2);//分子
        simplify(nn,nd);
    }

    public static void simplify(BigInteger nn, BigInteger nd) {//化简
        num[0] = nn.divide(nd);//整数
        nn = nn.mod(nd);
        BigInteger c = nd.gcd(nn);
        num[1] = nn.divide(c);//分子
        num[2] = nd.divide(c);//分母
    }

    public static void div(long a1, long a2, long b1, long b2) {
        BigInteger nd = BigInteger.valueOf(a1 * b2);//分母
        BigInteger nn = BigInteger.valueOf(a2 * b1);//分子
        simplify(nn,nd);
    }

    public static void add(long a1, long a2, long b1, long b2) {
        BigInteger nd = BigInteger.valueOf(a2 * b2);//分母
        BigInteger nn = BigInteger.valueOf(a1 * b2 + b1 * a2);//分子
        simplify(nn,nd);
    }

    public static void sub(long a1, long a2, long b1, long b2) {
        add(a1,a2,-b1,b2);
    }

    public static String toString(long a1, long a2) {
        long i1 = a1 / a2;//整数
        long j1 = a1 % a2;//分子
        if (j1 == 0 && i1 == 0) return "0";
        if (j1 == 0) return i1+"";
        if (i1 == 0) return a1 + "/" + a2;
        return i1 + " " + a1 + "/" + a2;
    }

    //day 36
    //看完答案后重写版（过了）
    public static void main_5_15_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String s = in.next();
            long n = Rational.parseNumerator(s);
            long d = Rational.parseDenominator(s);
            Rational r1 = new Rational(n,d);
            s = in.next();
            n = Rational.parseNumerator(s);
            d = Rational.parseDenominator(s);
            Rational r2 = new Rational(n,d);

            System.out.println(r1 +" + "+r2+ " = "+r1.add(r2));
            System.out.println(r1 +" - "+r2+ " = "+r1.sub(r2));
            System.out.println(r1 +" * "+r2+ " = "+r1.mul(r2));
            System.out.println(r1 +" / "+r2+ " = "+r1.div(r2));
        }
    }

    public static void main5_15_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLong()) {
            long a1 = in.nextLong();
            long a2 = in.nextLong();
            long b1 = in.nextLong();
            long b2 = in.nextLong();
            String s1 = toString(a1,a2);
            String s2 = toString(b1,b2);
            add(a1,a2,b1,b2);
            long a = num[0].longValue();
            long b = num[1].longValue();
            long c = num[1].longValue();
            String s3 = toString(b,c);
            System.out.println(s1 + " + " + s2 + " = " + a + " " + s3);

            sub(a1,a2,b1,b2);
            a = num[0].longValue();
            b = num[1].longValue();
            c = num[1].longValue();
            s3 = toString(b,c);
            System.out.println(s1 + " - " + s2 + " = " + a + " " + s3);

            mul(a1,a2,b1,b2);
            a = num[0].longValue();
            b = num[1].longValue();
            c = num[1].longValue();
            s3 = toString(b,c);
            System.out.println(s1 + " - " + s2 + " = " + a + " " + s3);

            div(a1,a2,b1,b2);
            a = num[0].longValue();
            b = num[1].longValue();
            c = num[1].longValue();
            s3 = toString(b,c);
            System.out.println(s1 + " - " + s2 + " = " + a + " " + s3);
        }
    }

    //day 35
    public static void main5_13_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String s = in.nextLine();
            String ss = in.nextLine();
            boolean flg = false;
            HashSet<String> a = new HashSet<>();
            String tmp = "";
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '"') {
                    if (!flg) {
                        flg = true;
                    } else {
                        a.add(tmp);
                        tmp = "";
                        flg = false;
                        i++;
                    }
                } else if (flg) {
                    tmp += s.charAt(i);
                } else if (s.charAt(i) == ','){
                    a.add(tmp);
                    tmp = "";
                } else {
                    tmp += s.charAt(i);
                }
            }
            if (tmp != "") {
                a.add(tmp);
            }
            if (a.contains(ss)) {
                System.out.println("Ignore");
            } else {
                System.out.println("Important!");
            }
        }
    }

    public static long factorial(long a) {
        long r = 1;
        while (a > 1) {
            r *= a--;
        }
        return r;
    }

    public static void main5_13_1(String[] args) {
        Scanner in = new Scanner(System.in);
        long[] t = new long[21];
        long[] fac = new long[21];
        t[1] = 0;
        fac[1] = 1;
        t[2] = 1;
        fac[2] = 2;
        int size = 2;
        while (in.hasNextInt()) {
            int n = in.nextInt();
            for (int i = size + 1; i <= n; i++, size++) {
                t[i] = (i - 1) * (t[i - 1] + t[i - 2]);
                fac[i] = i * fac[i - 1];
            }
            double p = 1.0 * t[n] / fac[n];
            System.out.printf("%05.2f%%\n",p * 100);
        }
    }

    //day 34
    public static void main5_12_2(String[] args) {
        Scanner in = new Scanner(System.in);
        long[] fib = new long[91];
        fib[1] = 1;
        fib[2] = 2;
        int size = 2;
        while (in.hasNextInt()) {
            int a = in.nextInt();
            for (int i = size + 1; i <= a; i++) {
                fib[i] = fib[i-1] + fib[i-2];
            }
            System.out.println(fib[a]);
        }
    }
//1 1 2 3 5 8
    public static void main5_12_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            String s = "";
            String t = in.nextLine();
            for (int i = 0; i < n; i++) {
                if (i > 0) {
                    s += ", ";
                }
                String ss = in.nextLine();
                if (ss.contains(",") || ss.contains(" ")) {
                    ss = "\"" + ss + "\"";
                }
                s += ss;
            }
            System.out.println(s);
        }
    }

    //day 33
    public static long sum(long[] array, int start, int end) {
        if (array == null || start >= array.length || end >= array.length) return 0;
        long ans = array[start];
        for (int i = start + 1; i <= end; i++) {
            ans += array[i];
        }
        return ans;
    }

    public static void main_5_11_2(String[] args) {
        Scanner in = new Scanner(System.in);
        long[] fib = new long[81];
        fib[1] = 1;
        fib[2] = 1;
        int size = 2;
        while (in.hasNextInt()) {
            int from = in.nextInt();
            int to = in.nextInt();
            for (int i = size + 1; i <= to; i++) {
                fib[i] = fib[i-1] + fib[i-2];
            }
            size = to;
            System.out.println(sum(fib,from,to));
        }
    }

    public static void main_5_11_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String s = in.next();
            String t = in.next();
            int count = 0;
            while (s.contains(t)) {
                count++;
                int i = s.indexOf(t);
                s = s.substring(i+t.length());
            }
            System.out.println(count);
        }
    }

    //day 32
    public static int yearIncome() {
        int[] table = {2,1,1,2,1,2,1,2,2,2,1,2,1};
        int[] days = {31,28,31,30,31,30,31,31,30,31,30,31};
        int a = 0;
        for (int i = 0; i < 12; i++) {
            a += table[i] * days[i];
        }
        return a;
    }

    public static int leapYear(int y1, int y2) {
        int ret = 0;
        for (int i = y1 + 1; i < y2; i++) {
            if (isLeapYear(i)) {
                ret++;
            }
        }
        return ret;
    }

    public static int countL(int y, int m1, int d1, int m2, int d2) {
        int[] table = {2,1,1,2,1,2,1,2,2,2,1,2,1};
        int[] days = {31,28,31,30,31,30,31,31,30,31,30,31};
        if (isLeapYear(y)) {
            days[1] = 29;
        }
        int ret = 0;
        if (m1 < m2) {
            for (int i = m1; i < m2-1 && i < 12; i++) {
                ret += table[i] * days[i];
            }
            ret += table[m1 - 1] * (days[m1 - 1] - d1 + 1);
            ret += table[m2 - 1] * d2;
        } else if (m1 == m2){
            ret += table[m1 - 1] * (d2 - d1 + 1);
        }
        return ret;
    }

    public static void main5_11_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int y1 = in.nextInt();
            int m1 = in.nextInt();
            int d1 = in.nextInt();
            int y2 = in.nextInt();
            int m2 = in.nextInt();
            int d2 = in.nextInt();
            int sum = 0;
            int yi = yearIncome();
            if (y2 > y1) {
                sum += countL(y1,m1, d1, 12, 31);
                sum += countL(y2,1, 1, m2, d2);
                if (y2 - y1 > 1) {
                    int c = y2 - y1 - 1;
                    int n = leapYear(y1, y2);
                    sum += c * yi + n;
                }
            } else if (y2 == y1) {
                sum += countL(y1,m1,d1,m2,d2);
            }
            System.out.println(sum);
        }
    }

    public static void main5_11_2(String[] args) {
        Scanner in = new Scanner(System.in);
        ArrayList<Integer> fib = new ArrayList<>();
        fib.add(1);
        fib.add(2);
        while (in.hasNextInt()) {
            int a = in.nextInt();
            if (a < fib.size()) {
                if (a > 24) {
                    System.out.printf("%06d\n",fib.get(a - 1));
                } else {
                    System.out.printf("%d\n",fib.get(a - 1));
                }
            } else {
                for (int i = fib.size(); i < a; i++) {
                    fib.add((fib.get(i-1) + fib.get(i - 2)) % 1000000);
                }
                if (a > 24) {
                    System.out.printf("%06d\n",fib.get(a - 1));
                } else {
                    System.out.printf("%d\n",fib.get(a - 1));
                }
            }
        }
    }

    //day 31
    //使用蔡勒公式 利用年月日计算 星期
    public static int dateOfWeek(int y, int m, int d) {
        if (m == 1 || m == 2) {
            m += 12;
            y--;
        }
        int c = y / 100;
        y %= 100;
        int w = (c / 4) - (2 * c) + y + (y / 4) + (13 * (m + 1) / 5) + d - 1;
        w = (w % 7 + 7) % 7;//这里要注意处理：第一%7：保证小于7 第二+7： 保证整数 第三%7：保证小于7
        return w == 0 ? 7 : w;
    }

    //以每月第一天的星期数为基准计算
    public static int getDate(int w, int n, int r) {
        int ans = 1;
        ans += (n - 1) * 7 + ((r - w + 7) % 7);
        return ans;
    }

    public static void main5_10_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int a = in.nextInt();
            System.out.println(a + "-01-01");

            int ret = dateOfWeek(a,1,1);
            int d = getDate(ret,3,1);
            System.out.println(a + "-01-"+d);

            ret = dateOfWeek(a,2,1);
            d = getDate(ret,3,1);
            System.out.println(a + "-02-"+d);

            ret = dateOfWeek(a,6,1);
            d = ret == 1 ? 6 : (ret - 2);
            System.out.println(a + "-05-"+(31 - d));

            System.out.println(a + "-07-04");

            ret = dateOfWeek(a,9,1);
            d = getDate(ret,1,1);
            System.out.println(a + "-09-0"+d);

            ret = dateOfWeek(a,11,1);
            d = getDate(ret,4,4);
            System.out.println(a + "-11-"+d);

            System.out.println(a + "-12-25");
            System.out.println();
        }
    }

    public static void getFactor(int n, ArrayList<Integer> list) {
        if (n == 0 || isPrime(n)) {
            if (n != 0) {
                list.add(n);
            }
            return;
        }
        for (int i = 2; i < n; i++) {
            if (n % i == 0) {
                list.add(i);
                n /= i;
                break;
            }
        }
        getFactor(n,list);
    }

    public static void main5_10_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int a = in.nextInt();
            ArrayList<Integer> list = new ArrayList<>();
            getFactor(a,list);
            System.out.print(a+" = ");
            for (int i = 0; i < list.size(); i++) {
                System.out.print(list.get(i));
                if (i < list.size()-1) {
                    System.out.print(" * ");
                }
            }
            System.out.println();
        }
    }

    //day 30
    public static void countFactor(int n, HashSet<Integer> set) {
        if (n == 0 || isPrime(n)) {
            if (n != 0) {
                set.add(n);
            }
            return;
        }
        for (int i = 2; i < n; i++) {
            if (n % i == 0) {
                set.add(i);
                n /= i;
                break;
            }
        }
        countFactor(n,set);
    }

    public static void main5_7_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int a = in.nextInt();
            HashSet<Integer> set = new HashSet<>();
            countFactor(a,set);
            System.out.println(set.size());
        }
    }

    public static void main5_7_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String s = in.nextLine();
            String pa = "VWXYZABCDEFGHIJKLMNOPQRSTU";
            String pb = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
            String ans = "";
            for (char c : s.toCharArray()) {
                if (pb.indexOf(c) != -1) {
                    ans += pa.charAt(pb.indexOf(c));
                } else {
                    ans += c;
                }
            }
            System.out.println(ans);
        }
    }

    //day 29
    public static void main5_7(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int a = in.nextInt();
            if (a == 0) {
                break;
            }
            if (a == 1) {
                System.out.println(0);
            } else if (a == 2 || a == 3) {
                System.out.println(1);
            } else {
                int count = 1;
                while (a > 3) {
                    count ++;
                    if (a % 3 == 0) {
                        a /= 3;
                    } else {
                        a = a / 3 + 1;
                    }
                }
                System.out.println(count);
            }
        }
    }

    //day 28
    public static void main4_28(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            if (n == 0) {
                break;
            }
            long start = (long)Math.pow(5,n) - 4;
            long remain = (long)Math.pow( 4, n) + n - 4;
            System.out.println(start + " " + remain);
        }
    }
//    static long[] array = new long[20];
//    static long[] num = new long[20];
//    static int count = 1;
//
//    public static boolean count(long i, int n) {
//        if (i % 5 == 1 && n == 1) return true;
//        if (i % 5 != 1) return false;
//        return count(i - (i / 5) - 1, n - 1);
//    }
//
//    public static void getNumber(int n) {
//        for (long i = num[count - 1] + 5; count < n; i += 5) {
//            if (count(i, n)) {
//                num[count] = i;
//                count++;
//            }
//        }
//        int a = n;
//        long b = num[count - 1];
//        while (a-- > 0) {
//            b--;
//            b -= b / 5;
//        }
//        array[count - 1] = b + n;
//    }
//
//    public static void main4_27(String[] args) {
//        Scanner in = new Scanner(System.in);
//        System.out.println(Integer.MAX_VALUE);
//        while (in.hasNextInt()) {
//            int n = in.nextInt();
//            num[0] = 1;
//            array[0] = 1;
//            if (n == 0) break;
//            if (n == 1) {
//                System.out.println("1 1");
//                continue;
//            }
//            if (count < n) {
//                for (int i = 2; i <= n; i++) {
//                    getNumber(i);
//                }
//            }
//            System.out.println(num[n - 1]+" "+ array[n - 1]);
//        }
//    }

//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        array[0] = 1;
//        num[0] = 0;
//        while (in.hasNextInt()) {
//            int n = in.nextInt();
//            if (n == 0) break;
//            if (n <= count)
//            for (int i = array[count-1]; i < Integer.MAX_VALUE; i += 4) {
//                if (count == n) break;
//                if (i % 5 == 1) {
//                    array[count] = i;
//                    num[count] = i / 5 + num[count - 1];
//                }
//            }
//
//        }
//    }

    //day27
    public static boolean Biger(String a, String b) {
        if (a.equals(b)) return false;
        if (a.length() > b.length()) return true;
        if (a.length() < b.length()) return false;
        //有两个变量的时候，忘记了j++ ，和上面count的错误相同
        //循环中变量的改变一定要小心！！！！！
        for (int i = 0, j = 0; i < a.length(); i++, j++) {
            char aa = a.charAt(i);
            char bb = b.charAt(j);
            if (aa > bb) return true;
            if (aa < bb) return false;
        }
        return true;
    }

    //a + b > c
    //a + c > b
    //b + c > a
    //看到数的范围就知道是大数的加法和比较
    public static void main_4_26_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {//这里必须用hasNext,如果用hashNextLine会出错
            StringBuilder a = new StringBuilder(in.next());
            StringBuilder b = new StringBuilder(in.next());
            StringBuilder c = new StringBuilder(in.next());
            if (Biger(add(a,b).toString(),c.toString())) {
                if (Biger(add(a,c).toString(),b.toString())) {
                    if (Biger(add(b,c).toString(),a.toString())) {
                        System.out.println("Yes");
                        continue;
                    }
                }
            }
            System.out.println("No");
        }
    }

    //day 26
    public static StringBuilder add(StringBuilder a, StringBuilder b){
        if (a.length() > b.length()) return add(b, a);//保证 a 是更短的串
        //这里 a 如果等于0或者为“”， 这个情形原来没有考虑到
        if (a.length() == 0 || a.length() == 1 && a.charAt(0) == '0') return b;
        StringBuilder ans = new StringBuilder();
        int flg = 0;
        int j = b.length() -1;
        for (int i = a.length()-1; i >= 0; i--, j--) {
            char aa = a.charAt(i);
            char bb = b.charAt(j);
            int n = (aa - '0') + (bb - '0') + flg;
            if (n > 9) {
                flg = 1;
                ans.append(n-10);
            } else {
                flg = 0;
                ans.append(n);
            }
        }
        while (j >= 0) {
            char bb = b.charAt(j);
            int n = bb-'0' + flg;
            if (n > 9) {
                flg = 1;
                ans.append(n - 10);
            }else {
                flg = 0;
                ans.append(n);
            }
            j--;
        }
        if (flg == 1) {
            ans.append(1);
        }
        return ans.reverse();
    }

    public static StringBuilder mul(String a, String b){
        if (a.length() > b.length()) return mul(b, a);//保证a是更小的串
        int flg = 0;
        StringBuilder num = new StringBuilder();
        //这里的count第一次考虑的位置错了，后来忘记count++
        for (int i = a.length()-1, count = 0; i >= 0; i--, count++) {
            char aa = a.charAt(i);
            StringBuilder ans = new StringBuilder();
            for (int j = b.length() -1; j >= 0; j--) {
                char bb = b.charAt(j);
                int n = (aa - '0') * (bb - '0') + flg;
                if (n > 9) {
                    flg = n / 10;
                    ans.append(n % 10);
                } else {
                    flg = 0;
                    ans.append(n);
                }
            }
            if (flg > 0) {
                ans.append(flg);
                flg = 0;
            }
            ans.reverse();
            //count的值需要一直保存着，所以这里不能直接用来减减计数，之前就犯过同样的错，
            //这里必须要复制一个值来计数！！！！
            //！！！！多次错误！
            int cnt = count;
            while (cnt-- > 0){
                ans.append(0);
            }
            num = add(num,ans);
        }
        return num;
    }

    public static boolean isBiger(String a, String b) {
        //一开始忽略了a中没有小数点的情况，导致出错了
        int end = a.indexOf('.');
        String sa = a.substring(0, end == -1 ? a.length() : end);
        if (sa.equals(b)) return true;
        if (sa.length() > b.length()) return true;
        if (sa.length() < b.length()) return false;
        //有两个变量的时候，忘记了j++ ，和上面count的错误相同
        //循环中变量的改变一定要小心！！！！！
        for (int i = 0, j = 0; i < sa.length(); i++, j++) {
            char aa = sa.charAt(i);
            char bb = b.charAt(j);
            if (aa > bb) return true;
            if (aa < bb) return false;
        }
        return true;
    }

    //这一个大数相乘再比较的问题，而且其中一个乘数是小数。
    //思路：先转换成整数进行计算，利用大数乘法和加法算出整数的周长，然后再加上前面忽略的小数点。
    //      需要考虑输入的整数中末尾包含零的情况，可以直接在main函数中处理
    //      最后还要写一个大数比较的方法
    public static void main4_26_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String s1 = in.next();
            String s2 = in.next();
            int count = 2;
            for (int i = s2.length() - 1; i >= 0; i--) {
                if (s2.charAt(i) == '0') {
                    count--;
                    s2 = s2.substring(0,i);
                } else {
                    break;
                }
            }
            String ss = "628";
            StringBuilder product = mul(ss,s2);
            if (count > 0) {
                product.insert(product.length() - count,'.');
            }
            while (count++ < 0) {
                product.append(0);
            }
            if (isBiger(product.toString(),s1)) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }

//        4181 0987 7711 0377 1393 7811
//        0001 0089 4101 3501 7501
    //day 25
    public static ArrayList<Integer> list = new ArrayList<>();

    public static int getN(int n){
        if (list.size() >= n) return list.get(n - 1);
        int num = 0;
        for (int i = list.size(); i < n; i++) {
            num = list.get(i-1) + list.get(i - 2);
            if (num > 10000) num %= 10000;
            list.add(num);
        }
        return num;
    }
    //星际迷航 理解+找规律+数字与字符串的转换&拼接
    public static void main4_25(String[] args) {
        Scanner in = new Scanner(System.in);
        list.add(1);
        list.add(2);
        while (in.hasNextInt()){
            int n = in.nextInt();
            String s = "";
            for (int i = 0; i < n; i++) {
                int a = in.nextInt();
                int num = getN(a);
                String ss = String.valueOf(num);
                while (ss.length() < 4){
                    ss = "0" + ss;
                }
                s += ss;
            }
            System.out.println(s);
        }
    }
    //分治
    public static void main4_24_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            char[] str = in.nextLine().toCharArray();
            if (str.length == 2){
                int sum = str[0]-'0' + str[1] - '0';
                if (sum > 9) System.out.println(sum - 9);
                else System.out.println(sum);
                continue;
            }
            for (int i = 1; i < str.length; i *= 2) {
                for (int j = i; j < str.length; j += i*2) {
                    int sum = str[j]-'0';
                    sum += str[j-i]-'0';
                    if (sum > 9){
                        sum = sum - 9;
                    }
                    char c = (char) ('0'+sum);
                    str[j-i] = c;
                }
            }
            System.out.println(str[0]);
        }
    }

//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        while (in.hasNextLine()) {
//            Stack<Integer> stack = new Stack<>();
//            String s = String.valueOf(in.nextLine());
//            while (true){
//                for (int i = 0; i < s.length(); i++) {
//                    stack.push(s.charAt(i) - '0');
//                }
//                long sum = 0;
//                while (!stack.isEmpty()){
//                    sum += stack.pop();
//                }
//                if (sum < 9){
//                    System.out.println(sum);
//                    break;
//                }
//                s = String.valueOf(sum);
//            }
//        }
//    }

//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        while (in.hasNextLong()) {
//            long n = in.nextLong();
//            Queue<Integer> queue = new LinkedList<>();
//            long sum = n;
//            while (sum > 9){
//                n = sum;
//                long count = 1;
//                while (n / 10 != 0){
//                    count *= 10;
//                    n /= 10;
//                }
//                while (count >= 1){
//                    queue.offer(n / count);
//                }
//                sum = 0;
//                while (!queue.isEmpty()){
//                    sum += queue.poll();
//                }
//            }
//            System.out.println(sum);
//        }
//    }

//    public static boolean getPanth(boolean[][] maze,int n, int m){
//        Stack<int[]> stack = new Stack<>();
//        int[] p = new int[]{n-1,m-1};
//        stack.push(p);
//        int i = n-1;
//        int j = m-1;
//        if (maze[i][j-1] && maze[i-1][j]){
//            getPanth()
//        }else if (maze[i][j-1]){
//
//        }else if (maze[i-1][j]){
//            stack.push(new int[]{i-1,j});
//            i--;
//        }
//
//    }

    public static boolean getPanth(boolean[][] maze, Stack<int[]> path, int n, int m, int l){
        if (n==0 && m==0 && path.isEmpty()){
            path.push(new int[]{0,0});
        }
        if (n==maze.length-1 && m==maze[0].length-1){
            return true;
        }
        if (n+1 < maze.length && maze[n+1][m] && l!= 2){//向下走
            path.push(new int[]{n+1,m});
            if (false == getPanth(maze,path,n+1,m,0)){
                path.pop();
            }else {
                return true;
            }
        }
        if (m+1<maze[0].length && maze[n][m+1] && l!=3){//向右走
            path.push(new int[]{n,m+1});
            if (false == getPanth(maze,path,n,m+1,1)){
                path.pop();
            }else return true;
        }
        if (n-1 >= 0 && maze[n-1][m] && l!=0){//往上走
            path.push(new int[]{n-1,m});
            if (false == getPanth(maze,path,n-1,m,2)){
                path.pop();
            }else return true;
        }
        if (m-1 >= 0 && maze[n][m-1] && l!=1){//往左走
            path.push(new int[]{n,m-1});
            if (false == getPanth(maze,path,n,m-1,3)){
                path.pop();
            }else return true;
        }
        return false;
    }

    //day24
    public static void main4_22_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int m = in.nextInt();
            boolean[][] maze = new boolean[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (in.nextInt() == 0){
                        maze[i][j] = true;
                    }
                }
            }
            Stack<int[]> path = new Stack<>();
            getPanth(maze,path, 0, 0,-1);
            ArrayList<String> arrayList = new ArrayList<>();
            while (!path.isEmpty()){
                int[] p = path.pop();
                arrayList.add("("+p[0]+","+p[1]+")");
            }
            for (int i = arrayList.size()-1; i >= 0; i--) {
                System.out.println(arrayList.get(i));
            }
        }
    }

    //day23
    //字符串编辑距离 动态规划
    //问题：字符串A变成字符串B所需要的操作次数
    //子问题：字符串A的一部分变成字符串B的一部分所需要的操作次数
    //状态转移F(i,j)：A的前i个字符转换成B的前j个字符所需要的距离
    //插入F(i, j): F(i, j-1) + 1
    //删除F(i, j): F(i-1, j) + 1
    //替换F(i, j): F(i-1, j-1) + A[i] == B[j] ? 0 : 1
    public static int getDistance(String s1, String s2){
        char str1[] = s1.toCharArray();
        char str2[] = s2.toCharArray();
        int len1 = s1.length();
        int len2 = s2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        //初始化
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i < dp[0].length; i++) {
            dp[0][i] = i;
        }
        //状态转移
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                //先计算插入和删除之间的最小值
                int a = Math.min(dp[i][j-1],dp[i-1][j]) + 1;
                //再和是否替换的结果进行比较
                if (str1[i-1] == str2[j-1]) {
                    dp[i][j] = Math.min(a,dp[i-1][j-1]);
                } else {
                    dp[i][j] = Math.min(a,dp[i-1][j-1] + 1);
                }
            }
        }
        return dp[len1][len2];
    }

    //递归 - 超时
    public static int getLevenshteinDistance(String s1, String s2,int l1, int l2){
        if (l1 == 0 || l2 == 0) return 0;
        if (s1.equals(s2)) return 0;
        if (s1.contains(s2)){
            String s = s1.replace(s2,"");
            return s.length();
        }
        int cos = 0;
        if (s1.charAt(l1 -1) != s2.charAt(l2 - 1)) cos = 1;
        int a = getLevenshteinDistance(s1,s2,l1,l2-1);//对s1增加
        int b = getLevenshteinDistance(s1,s2,l1-1,l2);//对s1删除
        int c = getLevenshteinDistance(s1,s2,l1-1,l2-1) + cos;//对s1修改
        a = a < b ? a : b;
        c = a < c ? a : c;
        return c;
    }

    public static void main4_21_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String s1 = in.nextLine();
            String s2 = in.nextLine();
            System.out.println(getDistance(s1,s2));
        }
    }

    //day22

    public static void main4_20_2(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        boolean flg = true;
        HashMap<Character,Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            if (map.containsKey(c)){
                map.put(c, map.get(c) + 1);
            }else {
                map.put(c, 1);
            }
        }
        for (char c : s.toCharArray()) {
            if (map.get(c) == 1){
                System.out.println(c);
                flg = false;
                break;
            }
        }
        if (flg){
            System.out.println(-1);
        }
    }

    public static int gcd(int a, int b){
        int c = a % b;
        while (c != 0){
            a = b;
            b = c;
            c = a % b;
        }
        return b;
    }

    public static void main4_20_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int a = in.nextInt();
            int[] array = new int[n];
            for (int i = 0; i < n; i++) {
                array[i] = in.nextInt();
                if (array[i] <= a){
                    a += array[i];
                }else {
                    a += gcd(a,array[i]);
                }
            }
            System.out.println(a);
        }
    }

    //day21

    public static int up(int[] a,int n,int index){
        if (n == 1) return index;
        if (n <= 4) {
            if (index == 0) index = n-1;
            else index--;
            return index;
        }
        if (index == 0){
            if (a[0] > 1) {
                for (int i = 0; i < 4; i++) {
                    a[i]--;
                }
            }else {
                int gap = n-4;
                for (int i = 0; i < 4; i++) {
                    a[i] += gap;
                }
                index = 3;
            }
        }
        else {
            index--;
        }
        return index;
    }

    public static int down(int[] a,int n, int index){
        if (n == 1) return index;
        if (n <= 4) {
            if (index == n-1) index = 0;
            else index++;
            return index;
        }
        if (index == 3){
            if (a[3] < n) {
                for (int i = 0; i < 4; i++) {
                    a[i]++;
                }
            }else {
                int gap = n-4;
                for (int i = 0; i < 4; i++) {
                    a[i] -= gap;
                }
                index = 0;
            }
        }
        else {
            index++;
        }
        return index;
    }

    public static void main_4_20_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            String s = in.next();
            int a[] = new int[]{1,2,3,4};
            int ret = 0;
            for (char c : s.toCharArray()) {
                if (c == 'U')
                    ret = up(a, n, ret);
                else if (c == 'D')
                    ret = down(a,n,ret);
            }
            for (int i = 0; i < Math.min(n,4); i++) {
                if (i > 0)
                    System.out.print(" ");
                System.out.print(a[i]);
            }
            System.out.println();
            System.out.println(a[ret]);
        }
    }

    public static void wash(int[] p){
        int n = p.length >> 1;
        Stack<Integer> stack = new Stack<>();
        int left = n-1;
        int right = p.length - 1;
        for (int i = 0; i < n; i++) {
            stack.push(p[right--]);
            stack.push(p[left--]);
        }
        for (int i = 0; i < p.length; i++) {
            p[i] = stack.pop();
        }
    }

    public static void main4_19_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int t = in.nextInt();
            while (t-- > 0){
                int n = in.nextInt();
                int k = in.nextInt();
                int[] poke = new int[2*n];
                for (int i = 0; i < 2*n; i++) {
                    poke[i] = in.nextInt();
                }
                for (int i = 0; i < k; i++) {
                    wash(poke);
                }
                for (int i = 0; i < 2*n; i++) {
                    System.out.print(poke[i]);
                    if (i < 2*n - 1) System.out.print(" ");
                }
                System.out.println();
            }
        }
    }

    //day20
    //改正
    public static int findCommonString2(String s1, String s2){
        if (s1 == s2) return s1.length();
        if (s1.length() < s2.length()) findCommonString(s2,s1);
        if (s1.contains(s2)) return s2.length();
        int max = 0;
        for (int i = 0; i < s1.length(); i++) {
            char c = s1.charAt(i);
            if (s2.contains(c + "")){
                int j = s2.indexOf(c);
                for (; j < s2.length(); j++) {
                    int l = i;
                    int l2 = j;
                    while (l < s1.length() && j < s2.length() && s1.charAt(l) == s2.charAt(l2)){
                        l++;
                        l2++;
                    }
                    if (l - i > max) max = l - i;
                }
            }
        }
        return max;
    }

    //通过版
    public static int findCommonString(String s1, String s2){
        if (s1 == s2) return s1.length();
        if (s1.length() < s2.length()) findCommonString(s2,s1);
        if (s1.contains(s2)) return s2.length();
        int max = 0;
        for (int i = 0; i < s1.length(); i++) {
            for (int j = 0; j < s2.length(); j++) {
                if (s1.charAt(i) == s2.charAt(j)){
                    int l1 = i + 1;
                    int l2 = j + 1;
                    while (l1 < s1.length() && l2 < s2.length() && s1.charAt(l1) == s2.charAt(l2)) {
                        l1++;
                        l2++;
                    }
                    if (l1 - i > max) max = l1-i;
                }
            }
        }
        return max;
    }

    public static void main_4_18_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String s1 = in.nextLine();
            String s2 = in.nextLine();
            System.out.println(findCommonString2(s1, s2));
        }
    }

    public static String reverseString(String s){
        if (s == null) return null;
        if (s.length() == 1) return s;
        int l = 0;
        int right = s.length()-1;
        char[] chars = s.toCharArray();
        while (l < right){
            char tmp = chars[l];
            chars[l] = chars[right];
            chars[right] = tmp;
            l++;
            right--;
        }
        String ret = new String(chars);
        return ret;
    }

    public static void main_4_18_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String s = in.nextLine();
            System.out.println(reverseString(s));
        }
    }

    //day 19
    public static String findLongestString1(String s1,String s2){
        if (s1.equals(s2)) return s1;
        if (s1.length() < s2.length()) findLongestString(s2,s1);//保证s1是长串
        if (s1.contains(s2)) return s2;
        String ss1 = findLongestString(s1,s2.substring(1,s2.length()));
        String ss2 = findLongestString(s1,s2.substring(0,s2.length()-1));
        return ss1.length() > ss2.length() ? ss1 : ss2;
    }

    public static String findLongestString2(String s1,String s2){
        if (s1.equals(s2)) return s1;
        if (s1.length() < s2.length()) findLongestString(s2,s1);//保证s1是长串
        if (s1.contains(s2)) return s2;
        int max = 0;
        String ans = "";
        for (int i = 0; i < s2.length(); i++) {
            int index = 0;
            int flg = 0;
            if (s1.contains(s2.charAt(i)+"")){
                flg++;
                index = s1.indexOf(s2.charAt(i)) + 1;
                int j = i+1;
                for (; j < s2.length(); j++) {
                    if (index < s1.length() && s1.charAt(index) == s2.charAt(j)){
                        index++;
                    }else {
                        break;
                    }
                }
                if (j - i > max){
                    max = j - i;
                    ans = s2.substring(i,j);
                }
            }
            if (flg >0){
                String tmp = s1.substring(index);
                while (tmp.contains(s2.charAt(i)+"")){
                    index = tmp.indexOf(s2.charAt(i)) + 1;
                    int j = i+1;
                    for (; j < s2.length(); j++) {
                        if (index < s1.length() && s1.charAt(index) == s2.charAt(j)){
                            index++;
                        }else {
                            break;
                        }
                    }
                    if (j - i > max){
                        max = j - i;
                        ans = s2.substring(i,j);
                    }
                    tmp = tmp.substring(index);
                }
            }
        }
        return ans;
    }

    //dp
    public static String findLongestString(String s1,String s2) {
        if (s1.length() > s2.length()) return findLongestString(s2,s1);//保证s1是更短的串
        int start = 0;
        int max = 0;
        int[][] dp = new int[s1.length()+1][s2.length()+1];
        for (int i = 1; i <= s1.length() ; i++) {
            for (int j = 1; j <= s2.length() ; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    if (dp[i][j] > max) {
                        max = dp[i][j];
                        start = i - max;
                    }
                }
            }
        }
        return s1.substring(start, start + max);
    }

    public static void main4_18_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String s1 = in.nextLine();
            String s2 = in.nextLine();
            System.out.println(findLongestString(s1, s2));
        }
    }

    public static int drink(int n){
        if (n == 0 || n == 1) return 0;
        if (n == 2 || n == 3) return 1;
        return n / 3 + drink(n / 3 + (n % 3));
    }

    public static void main4_18_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (true) {
            int n = in.nextInt();
            if (n == 0 ) break;
            System.out.println(drink(n));
        }
    }

    public static ArrayList<Integer> getNum(int line){
        ArrayList<Integer> list = new ArrayList();
        if (line == 4){
            list.add(6);
            list.add(7);
            return list;
        }
        ArrayList<Integer> lastLine = getNum(line-1);
        for (int i = 0; i < line-2; i++) {
            if (i == 0){
                list.add(line+lastLine.get(0));
            } else if (i==1){
                list.add(lastLine.get(i)+lastLine.get(i-1)+line-2);
            } else if (i == line-1){
                int num = lastLine.get(i-1) + lastLine.get(i-2)*2;
                list.add(num);
            } else {
                int num = lastLine.get(i)+lastLine.get(i-1)+lastLine.get(i-2);
                list.add(num);
            }
        }
        return list;
    }

    public static int getIndex(ArrayList<Integer> list){
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) % 2 == 0){
                return i+3;
            }
        }
        return -1;
    }

    //4_15 day 18
    //通配符 dp数组
    public static void main4_15_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String t = in.nextLine().toLowerCase(Locale.ROOT);
            String s = in.nextLine().toLowerCase(Locale.ROOT);
            boolean[][] a = new boolean[s.length()+1][t.length()+1];
            a[0][0] = true;
            for (int i = 0; i < s.length()+1; i++) {
                for (int j = 1; j < t.length()+1; j++) {
                    if (t.charAt(j-1) == '*') {
                        if (i == 0) {
                            a[i][j] = a[i][j-1];
                        } else if (s.charAt(i-1) == '.' || (s.charAt(i-1) >= 'a' && s.charAt(i-1) <= 'z') || (s.charAt(i-1) >= '0' && s.charAt(i-1) <= '9')){
                            a[i][j] = a[i][j-1] || a[i-1][j] || a[i-1][j-1];
                        }
                    } else {
                        if (i > 0 && isMatch(t.charAt(j-1),s.charAt(i-1))) {
                            a[i][j] = a[i-1][j-1];
                        }
                    }
                }
            }
            System.out.println(a[s.length()][t.length()]);
        }
    }

    public static boolean isMatch(char a, char b) {
        if (a == '?' && ((b >= 'a' && b <= 'z') || (b >= '0' && b <= '9'))) return true;
        return a == b;
    }



//    没过………………
//    public static boolean matchSign(String s){
//        for (char ch : s.toCharArray()) {
//            if (ch != '*' || ch != '?') return false;
//        }
//        return true;
//    }
//
//    public static boolean isLegal(char c){
//        return Character.isDigit(c) || (c >= 'a' && c <= 'z');
//    }
//
//    public static int isLegalString(String s){
//        for (char c : s.toCharArray()) {
//            if (!isLegal(c)) return s.indexOf(c);
//        }
//        return -1;
//    }
//
//    public static boolean _match(String s1, String s2){
//        if (!s1.contains("?") && !s1.contains("*")) return s1.equals(s2);
//        int l1 = 0;
//        int r1 = s1.length()-1;
//        int l2 = 0;
//        int r2 = s2.length()-1;
//        while (l1 < r1 && l2 < r2){
//            if (matchSign(s1.substring(l1,r1+1))) return true;
//            while (l1 <= r1 && l2 <= r2 && s1.charAt(l1) == s2.charAt(l2)){
//                l1++;
//                l2++;
//            }
//            while (l1 <= r1 && l2 <= r2 && s1.charAt(r1) == s2.charAt(r2)){
//                r1--;
//                r2--;
//            }
//            if (l1 < r1 && l2 < r2 && (s1.charAt(l1) != '*' && s1.charAt(l1) != '?')
//                    || (s1.charAt(r1) != '*' && s1.charAt(r1) != '?')){
//                return false;
//            }//两个都没走完，并且还没有遇到通配符
//            if (l1 > r1 && l2 < r2) return false;//s1走完 s2没走完
//            if (l1 > r1 && l2 > r2) return true;//s1走完 s2走完
//            if (l1 < r1 && l2 > r2){//s1没走完 s2走完
//                while (l1 < r2 && s1.charAt(l1) == '*') l1++;
//                while (l1 < r2 && s1.charAt(r1) == '*') r1--;
//                if (l1 >= r2) return true;
//                return false;
//            }
//            //都没走完并且遇到了通配符
//            while (l1 <= r1 && l2 <= r2 && s1.charAt(l1)=='?' && isLegal(s2.charAt(l2))){
//                l1++;
//                l2++;
//            }
//            while (l1 <= r1 && l2 <= r2 && s1.charAt(r1)=='?' && isLegal(s2.charAt(r2))){
//                r1--;
//                r2--;
//            }
//            int pos = isLegalString(s2);
//            if (pos == -1 && l1 > l2) return true;
//            if (l1 <= r1 && s1.charAt(l1)=='*'){
//                while (l1 <= r1 && s1.charAt(l1)=='*') l1++;
//                if (l1 <= r1 && !s2.substring(l2,r2+1).contains(s1.substring(l1,l1+1))) return false;
//                pos = isLegalString(s2.substring(l2,r2+1));
//                if (pos == -1 && l1 > r1) return true;
//                if (pos ==-1) pos = s2.substring(l2,r2+1).indexOf(s1.charAt(l1));
//                l2 = l2 + pos;
//                l1++;
//            }
//            if (l1 < r1 && s1.charAt(r1)=='*'){
//                while (l1 <= r1 && s1.charAt(r1)=='*') r1--;
//                if (l1 <= l1 && !s2.substring(l2,r2+1).contains(s1.substring(r1,r1+1))) return false;
//                pos = isLegalString(s2.substring(l2,r2+1));
//                if (pos == -1 && l1 > r1) return true;
//                if (pos ==-1) pos = s2.substring(l2,r2+1).indexOf(s1.charAt(l1));
//                l2 = l2 + pos;
//                r1--;
//            }
//        }
//        if (l1 > r1 && l2 > r2) return true; //s1走完 s2走完
//        if (l1 > r1 && l2 < r2) return false;//s1走完 s2没走完
//        if (l1 < r1 && l2 > r2){             //s1没走完 s2走完
//            while (l1 < r2 && s1.charAt(l1) == '*') l1++;
//            while (l1 < r2 && s1.charAt(r1) == '*') r1--;
//            if (l1 >= r2) return true;
//            return false;
//        }
//        if (l1 == r1 || l2 == r2){
//            if (l1 == r1 && l2 == r2){
//                if (s1.charAt(l1) == s2.charAt(l2)) return true;
//                return false;
//            }
//            else if (l1 == r1){//s2没走完
//                if ((s1.charAt(l1) == '*' || s1.charAt(l1) == '?') && isLegal(s2.charAt(l2))) return true;
//                return false;
//            }else {//s1没走完 s2剩下一个
//                if (s1.charAt(l1) == s2.charAt(l2)){
//                    l1++;
//                    while (l1 <= r1 && s1.charAt(l1) == '*') l1++;
//                    if (l1 <= r1) return false;
//                    else return true;
//                }
//                if (s1.charAt(r1) == s2.charAt(l2)){
//                    r1--;
//                    while (l1 <= r1 && s1.charAt(l1) == '*') l1++;
//                    if (l1 <= r1) return false;
//                    else return true;
//                }
//                if (s1.contains(s2.substring(l2,l2+1))){
//                    int pos = s1.indexOf(s2.charAt(l2));
//                    s1 = s1.substring(l1,pos);
//                    for (char c: s1.toCharArray()) {
//                        if (c != '*') return false;
//                    }
//                    s1 = s1.substring(pos+1,r1+1);
//                    for (char c: s1.toCharArray()) {
//                        if (c != '*') return false;
//                    }
//                    return true;
//                }
//                if (!isLegal(s2.charAt(l2))) return false;
//                if (s1.charAt(l1) == '*') return true;
//                return false;
//            }
//        }
//        return true;
//    }
//
//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        while (in.hasNextLine()) {
//            String s1 = in.nextLine();
//            String s2 = in.nextLine();
//            s1 = s1.toLowerCase();
//            s2 = s2.toLowerCase();
//            System.out.println(_match(s1, s2));
//        }
//    }

//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        while (in.hasNextLine()) {
//            String s1 = in.nextLine();
//            String s2 = in.nextLine();
//            s1.toLowerCase();
//            s2.toLowerCase();
//            boolean flg = false;
//            if (!s1.contains("*") && !s1.contains("?")){
//                System.out.println(s1.equals(s2));
//            }else if (!s1.contains("*")){//只含？
//                int pos = s1.indexOf("?");
//                String ss1 = s1.substring(0,pos);
//                String ss2 = s2.substring(0,pos);
//                while (ss1.length()>0 && ss1.equals(ss2) && ss1.contains("?")){
//                    ss1 = s1.substring(pos+1);
//                    ss2 = s2.substring(pos+1);
//                    pos = ss1.indexOf("?");
//                    ss1 = ss1.substring(0,pos);
//                    ss2 = ss2.substring(0,pos);
//                }
//                if (){
//                    System.out.println(flg);
//                }
//            }else if (!s1.contains("?")){//只含*
//                int pos = s1.indexOf("*");
//
//            }else {
//
//            }
//        }
//    }

    public static void main4_15_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            if (n == 1 || n==2) System.out.println(1);
            else {
                int a = 1;
                int b = 1;
                int c = 0;
                while (n > 2){
                    c = a + b;
                    a = b;
                    b = c;
                    n--;
                }
                System.out.println(c);
            }
        }
    }

    //4_14 day 17
    //杨辉三角的变形 这题还是得找规律啊
    public static void main4_14_2(String[] args){
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            if (n == 1 || n == 2)
                System.out.println(-1);
            else if (n % 2 == 1)
                System.out.println(2);
            else if (n % 4 == 0)
                System.out.println(3);
            else
                System.out.println(4);
        }
    }

    //没过
    public static void main4_14(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int a = in.nextInt();
            if (a == 1 || a ==2) {
                System.out.println(-1);
            }else if (a % 2 == 1) {
                System.out.println(2);
            }
            else {
                ArrayList<Integer> list = getNum(a);
                System.out.println(getIndex(list));
            }
        }
    }

    //4_14 day 16

    public static void main4_14_answer(String[] args){
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        String[] pp = str.split("-");//split方法的妙用
        String[] p1 = pp[0].split(" ");
        String[] p2 = pp[1].split(" ");
        if (pp[0].equals("joker JOKER")||pp[1].equals("joker JOKER")) {
            System.out.println("joker JOKER");
        }else if (p1.length == p2.length) {//字符串，避免了10两个字符产生的歧义
            String p = "34567891JQKA2";//妙用字符串
            if (p.indexOf(p1[0].charAt(0)) > p.indexOf(p2[0].charAt(0))) {
                System.out.println(pp[0]);
            }else {
                System.out.println(pp[1]);
            }
        }else if (p1.length == 4) {
            System.out.println(pp[0]);
        }else if (p2.length == 4) {
            System.out.println(pp[1]);
        }else {
            System.out.println("ERROR");
        }
    }

    public static String comParePoker(String s){
        if (s == null || s.length() == 0) return "";
        if (s.contains("10")){
            s = s.replace("10","o");
        }
        int pos = s.indexOf('-');
        String s1 = s.substring(0,pos);
        String s2 = s.substring(pos+1);
        //对王
        if (s.contains("joker JOKER")) return s1.contains("joker JOKER") ? s1 : s2;
        //炸牌
        String ret = s1;
        if ((s1.length() == 7 || s2.length() == 7 ) && s1.length() != s2.length())
            ret = s1.length() == 7 ? s1 : s2;
        else if (s.contains("JOKER")) return s1.contains("JOKER") ? s1 : s2;
        else if (s.contains("joker")) return s1.contains("joker") ? s1 : s2;
        else if (s1.length() != s2.length()) return "ERROR";//剩下的牌不存在比较关系
        else {
            HashMap<Character, Integer> hashMap = new HashMap<>();
            hashMap.put('3', 1);
            hashMap.put('4', 2);
            hashMap.put('5', 3);
            hashMap.put('6', 4);
            hashMap.put('7', 5);
            hashMap.put('8', 6);
            hashMap.put('9', 7);
            hashMap.put('o', 8);
            hashMap.put('J', 9);
            hashMap.put('Q', 10);
            hashMap.put('K', 11);
            hashMap.put('A', 12);
            hashMap.put('2', 13);
            ret = hashMap.get(s1.charAt(0)) > hashMap.get(s2.charAt(0)) ? s1 : s2;
        }
        if (ret.contains("o")){
            ret = ret.replaceAll("o","10");
        }
        return ret;
    }

    public static void mainday16_2(String[] args) {

        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String s = in.nextLine();
            System.out.println(comParePoker(s));
        }
    }

    public static void main_14_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int count = 0;
            for (int i = 4; i <= n; i++) {
                int sum = 1;
                for (int j = 2; j <= Math.sqrt(i); j++) {
                    if (i % j == 0){
                        sum += (i / j) + j;
                    }
                    if (sum >= i) break;
                }
                if (i % Math.sqrt(i) == 0) sum += Math.sqrt(i);
                if (sum == i){
                    count++;
                }
            }
            System.out.println(count);
        }
    }

    //4_12 day 15
    public static void main4_12_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int a = in.nextInt();
            int count = 0;
            while (a != 0){
                int b = a - 1;
                a = a & b;
                b = a - 1;
                count++;
            }
            System.out.println(count);
        }
    }

    //4_11 day 14
    public static int factorial(int num){
        int ret = 1;
        while (num >= 1){
            ret *= num--;
        }
        return ret;
    }

    public static int combinationNumber(int n, int r){
        return factorial(n) / (factorial(r) * (factorial(n - r)));
    }

    public static int sum(int[] array){
        int ans = 0;
        for (int i = 0; i < array.length; i++) {
            ans += array[i];
        }
        return ans;
    }

    public static int sum(ArrayList<Integer> array){
        int ans = 0;
        for (int i = 0; i < array.size(); i++) {
            ans += array.get(i);
        }
        return ans;
    }

    public static int product(int[] array){
        int ans = 0;
        for (int i = 0; i < array.length; i++) {
            ans *= array[i];
        }
        return ans;
    }

    public static int product(ArrayList<Integer> array){
        int ans = 1;
        for (int i = 0; i < array.size(); i++) {
            ans *= array.get(i);
        }
        return ans;
    }

    public static int count(int[] array, int end){
        if (end <= 1) return 1;
        if (array[end] == array[end - 1]){
            return count(array, end - 1) + 1;
        }else {
            return count(array, end - 1) * 2;
        }
    }

    public static int count(ArrayList<Integer> array, int end){
        if (end <= 2) return 1;
        if (array.indexOf(end - 1) == array.indexOf(end - 2)){
            return count(array, end - 1) + 1;
        }else {
            return count(array, end - 1) * 2;
        }
    }

    public static int luckyPackages(int[] balls, int end){
        if (sum(balls) > product(balls)){
            return count(balls, end);
        }else {
            return luckyPackages(balls, end - 1);
        }
    }

    public static int luckyPackages(ArrayList<Integer> arrayList){
        if (sum(arrayList) > product(arrayList)){
            return count(arrayList,arrayList.size());
        }
        int ans = 0;
        for (int i = arrayList.size()-1; i > 0 ; i--) {
            int remove = arrayList.remove(i);
            ans += luckyPackages(arrayList);
            arrayList.add(remove);
        }
        return ans;
    }

    public static int count(int[] a, int n, int pos, int sum, int mul) {
        int count = 0;
        for (int i = pos; i < n; i++) {
            sum += a[i];
            mul *= a[i];
            if (mul < sum) {
                count += 1 + count(a,n,i+1,sum,mul);
            }else if (a[i] == 1) {
                count += count(a,n,i+1,sum,mul);
            }else break;
            sum -= a[i];
            mul /= a[i];
            while (i < n-1 && a[i] == a[i+1]) {
                i++;
            }
        }
        return count;
    }

    public static void main4_11_2_pass(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = in.nextInt();
            }
            Arrays.sort(a);//这一步忘记了，导致运行超时
            System.out.println(count(a,n,0,0,1));
        }
    }

    public static void main4_11(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            ArrayList<Integer> arrayList = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                arrayList.add(in.nextInt());
            }
            System.out.println(luckyPackages(arrayList));
        }
    }

    public static void main4_11_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int[] balls = new int[n];
            for (int i = 0; i < n; i++) {
                balls[i] = in.nextInt();
            }
            Arrays.sort(balls);
            System.out.println(luckyPackages(balls, balls.length - 1));
        }
    }

    public static boolean isLeapYear(int year) {
        return year % 400 == 0 || (year % 4 == 0 && year % 100 != 0);
    }

    public static int countDays(int year, int month, int day){
        int[] days = new int[]{31,28,31,30,31,30,31,31,30,31,30,31};
        int tmp = day;
        for (int i = 0; i < month-1; i++) {
            tmp += days[i];
        }
        return (month > 2 && isLeapYear(year)) ? tmp + 1 : tmp;
    }

    public static void main4_11_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int year = in.nextInt();
            int month = in.nextInt();
            int day = in.nextInt();
            System.out.println(countDays(year,month,day));
        }
    }

    //4_3 day 13
    public static List<Integer> gcd(int n) {
        List<Integer> list = new ArrayList<>();
        for (int i = 2; i * i <= n ; i++) {
            if (n % i == 0) {
                list.add(i);
                if (n / i != i) {
                    list.add(n/i);
                }
            }
        }
        return list;
    }

//    public static int jump(long n, long m){
//        if (n>m)return -1;
//        if (n==m)return 0;
//        for (long i = n-1; i > 1; i--) {
//            if (n%i==0){
//                int j = jump(n+i,m);
//                if (j!=-1) return j+1;
//            }
//        }
//        return -1;
//    }

    public static int jump(int n, int m) {
        int[] step = new int[m+1];
        for (int i = 0; i < m+1; i++) {
            step[i] = Integer.MAX_VALUE;
        }
        step[n] = 0;
        for (int i = n; i < m+1; i++) {
            if (step[i] == Integer.MAX_VALUE) continue;
            List<Integer> list = gcd(i);
            for (int num : list) {
                if (i + num <= m) {
                    step[i + num] = Math.min(step[i + num], step[i] + 1);
                }
            }
        }
        return step[m] == Integer.MAX_VALUE ? -1 : step[m];
    }

    public static void main4_4_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int m = in.nextInt();
            System.out.println(jump(n,m));
        }
    }
    //4_3_2
    public static void main4_3_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String s = in.nextLine();
            ArrayList<String> arrayList = new ArrayList<String>();
            boolean flg = false;
            int start = 0;
            int i = 0;
            for (; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c==' '&& !flg && start<i){
                    arrayList.add(s.substring(start,i));
                    start = i+1;
                }else if (c=='"' && !flg){
                    flg = true;
                }else if (c=='"'&& flg && start+1<i){
                    arrayList.add(s.substring(start+1,i));
                    start = i+2;
                    flg = false;
                }
            }
            if (start<i){
                arrayList.add(s.substring(start,i));
            }
            System.out.println(arrayList.size());
            for (String ss:arrayList) {
                System.out.println(ss);
            }
        }
    }


    //4_2 day 12
    public static boolean isPrime(int a){
        for (int i = 2; i <= Math.sqrt(a); i++) {
            if (a % i ==0)return false;
        }
        return true;
    }

    public static void main4_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int min = n;
            int a = n;
            for (int i = 0; i <= n>>1; i++) {
                if (isPrime(i)==true && isPrime(n-i)==true && min>(n-i-i)){
                    min = n-i-i;
                    a = i;
                }
            }
            System.out.println(a);
            System.out.println(n-a);
        }
    }

    //4_1 day11
    public static void main4_1_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int count = 0;
            int max = 0;
            for (int i = 0; i < 31; i++) {
                if ((n>>>i & 1) ==1){
                    count++;
                    if (max<count)max=count;
                }else {
                    count = 0;
                }
            }
            System.out.println(max);
        }
    }

    //3_31 day 10
    public static void main3_31_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String s = in.nextLine();
            int score = 0;//分数
            int len = s.length();//密码长度
            if (len<=4)score+=5;
            else if (len>=8)score+=25;
            else score+=10;

            int c = 0;//字母，没有为0，小写为-1，大写为1，都有为2
            int n = 0;//数字
            int flg = 0;//符号
            for (int i = 0; i < len; i++) {
                char ch = s.charAt(i);
                if (ch>='0'&&ch<='9')n++;
                else if (ch>='a'&& ch<='z'){
                    if (c==2)continue;
                    if (c==1)c=2;
                    else c=-1;
                }else if (ch>='A'&& ch<='Z'){
                    if (c==2)continue;
                    if (c==-1)c=2;
                    else c=-1;
                }else if (ch>=0x21 && ch<=0x2F || ch>=0x3A && ch<=0x40 || ch>=0x5B && ch<=0x60 || ch>=0x7B && ch<=0x7E )
                    flg++;
            }
            if (c == 2) score+=20;
            else if (c != 0) score+=10;

            if (n > 1) score+=20;
            else if (n > 0)score+=10;

            if (flg > 1)score+=25;
            else if (flg > 0)score+=10;

            if (c == 2 && n > 0 && flg > 0) score+=5;
            else if (c != 0 && n > 0 && flg > 0) score+=3;
            else if (c != 0 && n > 0) score+=2;

            if (score>=90) System.out.println("VERY_SECURE");
            else if (score>=80) System.out.println("SECURE");
            else if (score>=70) System.out.println("VERY_STRONG");
            else if (score>=60) System.out.println("STRONG");
            else if (score>=50) System.out.println("AVERAGE");
            else if (score>=25) System.out.println("WEAK");
            else System.out.println("VERY_WEAK");
        }
    }

    //3_30 day 9

    public static int way(int n,int m){
        if (n==1 || m == 1){
            return 1;
        }
        return way(n,m-1)+way(n-1,m);
    }

    public static void main3_30_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int m = in.nextInt();
            System.out.println(way(n+1,m+1));
        }
    }

    //3_29 day 8
    public static void main3_29_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int a = in.nextInt();
            int b = in.nextInt();
            int num = a*b;
            int c = a%b;
            while (c>0){
                a = b;
                b = c;
                c = a%b;
            }
            System.out.println(num/b);
        }
    }

    public static void main3_29_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()){
            int n = in.nextInt();
            in.nextLine();
            String[] strings = new String[n];
            for (int i = 0; i < n; i++) {
                strings[i] = in.nextLine();
            }
            boolean flg1 = false;
            boolean flg2 = false;
            for (int i = 1; i < n-1; i++) {
                if (strings[i].compareTo(strings[i-1])<0){
                    flg1 = true;
                    break;
                }
            }
            for (int i = 1; i < n; i++) {
                if (strings[i].length()<strings[i-1].length()){
                    flg2 = true;
                    break;
                }
            }
            if (flg1){
                if (flg2){
                    System.out.println("none");
                }else {
                    System.out.println("lengths");
                }
            }else if (flg2){
                System.out.println("lexicographically");
            }else {
                System.out.println("both");
            }
        }
    }

    //3_28 day 7
    public static void main3_28(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            if (n==0||n==1) System.out.println(0);
            else {
                int a = 0;
                int b = 1;
                int c = a+b;
                while (c<n){
                    a = b;
                    b = c;
                    c = a+b;
                }
                System.out.println((n - b > c - n) ? c - n : n - b);
            }
        }
    }

    //3_27 day 6
    public static void main3_27(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLong()) {
            long W = in.nextLong();//3
            long H = in.nextLong();//3
            long w = W / 4;    //0
            long i = W % 4;    //3
            long h = H / 4;    //0
            long j = H % 4;    //3
            long sum = H * (w << 1);
            if (i < 3) {
                sum += i * h * 2;
                if (j < 3) {
                    sum += i * j;
                } else {//j==3
                    sum += i * 2;
                }
            } else {//i==3
                sum += 2 * h * 2 + h*2;
                if (j < 3) {
                    sum += 2 * j;
                } else if (j == 3) {
                    sum += 2 * 2 + 1;
                }
            }
            System.out.println(sum);
        }
    }

//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        while (in.hasNextLong()) {
//            long W = in.nextLong();//6
//            long H = in.nextLong();//6
//            long w = W/2;    //3
//            long i = W%4;    //2
//            long h = H/4;    //1
//            long j = H%4;    //2
//            long sum = 2*H*((w+1)>>1);
//            if (i == 1 && j>0 ){
//                sum += h*2+(j>2?2:j);
//            }else if (i==3 && j==3){
//                sum += h*2 +1;
//            }
//            System.out.println(sum);
//        }
//    }

    //3_24 day 5
    //动态规划
    //找到状态转移方程：max(dp[i]) = max(dp[i-1]+array[i],array[i]);
    public static void main3_24(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int[] array = new int[n];
            for (int i = 0; i < n; i++) {
                array[i] = in.nextInt();
            }
            int sum = array[0];
            int max = array[0];
            for (int i = 1; i < n; i++) {
                sum = Math.max(sum+array[i], array[i]);
                max = Math.max(sum, max);
            }
            System.out.println(max);
        }
    }

    public static void main3_24_2 (String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int[] array = new int[n];
            int sum = 0;
            int max = 0;
            for (int i = 0; i < n; i++) {
                array[i]= in.nextInt();
                if (i == 0){
                    sum = array[i];
                }
                if (i>0){
                    if (Math.abs(array[i]-array[i-1])<=1){//连续的
                        if (sum<0){
                            sum = 0;
                        }
                        sum += array[i];
                    }else {//不连续
                        sum = array[i];
                    }
                    if (sum>max){
                        max = sum;
                    }
                }else {
                    max = sum;
                }
            }
            System.out.println(max);
        }
    }

    public static boolean Is(String s) {
        int left = 0;
        int right = s.length()-1;
        while (left<right){
            if (s.charAt(left)!=s.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static void main3_24_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String a = in.nextLine();
            String b = in.nextLine();
            int count = 0;
            for (int i = 0; i <= a.length() ; i++) {
                StringBuilder s = new StringBuilder();
                s.append(a,0,i);
                s.append(b);
                s.append(a,i,a.length());
                if (Is(s.toString())==true){
                    count++;
                }
            }
            System.out.println(count);
        }
    }

    //3_23 day4
    public static void main3_23_2(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] array = new char[]{'A','B','C','D','E','F'};
        while (in.hasNextInt()){
            int M = in.nextInt();
            int N = in.nextInt();
            StringBuilder s = new StringBuilder();
            boolean flg = false;
            if (M<0){
                M = -M;
                flg = true;
            }
            while (M>0){
                int i = M%N;
                if (i<10){
                    s.append(i);
                }else {
                    s.append(array[i-10]);
                }
                M/=N;
            }
            if (s.length()==0){
                System.out.println(0);
            }
            if (flg == true){
                s.append("-");
            }
            s.reverse();
            System.out.println(s.toString());
        }
    }

    //3_23_1
    public static void main3_23_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()){
            int[] array = new int[4];
            for (int i = 0; i < 4; i++) {
                array[i] = in.nextInt();
            }
            int A,B,C;
            boolean flg = false;
            for (int i = 0; i <= 30 && !flg; i++) {
                A = i;
                B = A - array[0];
                C = B - array[1];
                if (B<0 ||C <0){
                    continue;
                }
                if (array[2]==A+B && array[3]==B+C){
                    System.out.println(A+" "+B+" "+C);
                    flg = true;
                }
            }
            if (!flg){
                System.out.println("No");
            }
        }
    }

    public static void main3_23_11(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()){
            int[] array = new int[4];
            for (int i = 0; i < 4; i++) {
                array[i] = in.nextInt();
            }
            int A = (array[0]+array[2])>>1;
            int B = (array[1]+array[3])>>1;
            int C = (array[3]-array[1])>>1;
            if (A>=0 && B>=0 && C>=0){
                System.out.println(A+" "+B+" "+C);
            }else {
                System.out.println("No");
            }
        }
    }

    //3_22_1 第三天
    public static void main3_22(String[] args) {
        int[] a = new int[]{1,2,3,2,2,2,5,4,2};
        Solution solution = new Solution();
        System.out.println(solution.MoreThanHalfNum_Solution(a));
    }
    public static void main3_22_1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String str = in.nextLine();
            int max = 0;
            int len = 0;
            int maxIndex = 0;
            int index = 0;
            for (int i = 0; i < str.length(); i++) {
                char c = str.charAt(i);
                if (c>='0' && c<='9'){
                    if (len == 0){
                        index = i;
                    }
                    len++;
                    if (max < len){
                        max = len;
                        maxIndex = index;
                    }
                }else {
                    len = 0;
                }
            }
            System.out.println(str.substring(maxIndex, maxIndex + max));
        }
    }

    //3.21 第二天
    public static void main3_21_2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String str = in.nextLine();
            StringTokenizer st = new StringTokenizer(str," ",true);
            ArrayList<String> arrayList = new ArrayList<>();
            StringBuilder sb = new StringBuilder();
            while (st.hasMoreTokens()){
                arrayList.add(st.nextToken());
            }
            Collections.reverse(arrayList);
            for (String s : arrayList) {
                sb.append(s);
            }
            System.out.println(sb);
        }
    }

    //3_21_1
    public static void main3_21_1(String[] args) {
        Scanner in = new Scanner(System.in);
        int count = 1;
        int flg = 0;//0表示非递增，1表示非递减，2表示两者都不是的情况
        int n = in.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = in.nextInt();
            if (i > 1){
                if (array[i]<array[i-1]){//非递增
                    if (flg == 1){
                        count++;
                        flg = 2;
                    } else {
                        flg = 0;
                    }
                }else if (array[i]>array[i-1]){//非递减
                    if (flg == 0){
                        count++;
                        flg = 2;
                    }else {
                        flg = 1;
                    }
                }
            }else if (i == 1){
                if (array[i]<array[i-1]){//非递增
                    flg = 0;
                }else if (array[i]>array[i-1]){//非递减
                    flg = 1;
                }else {//相等
                    flg = 2;
                }
            }
        }
        System.out.println(count);
    }

    //3.20 第一天
    public static void main111(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        ArrayList<Integer> a = new ArrayList<>();
        for (int i = 0; i < t*3 ; i++) {
            a.add(in.nextInt());
        }
        a.sort(Comparator.naturalOrder());
        int sum = 0;
        int r = t*3-1;
        while (r<t){
            sum += a.get(r-1);
            r-=3;
        }
        System.out.println(sum);
    }

    //这题改成long类型就对了
    public static void main11(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        ArrayList<Integer> a = new ArrayList<>();
        for (int i = 0; i < t*3 ; i++) {
            a.add(in.nextInt());
        }
        a.sort(Comparator.naturalOrder());
        int sum = 0;
        for (int i = t; i < t*3; i+= 2) {
            sum += a.get(i);
        }
        System.out.println(sum);
    }

    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        ArrayList<Integer> a = new ArrayList<>();
        for (int i = 0; i < t*3 ; i++) {
            a.add(in.nextInt());
        }
        a.sort(Comparator.naturalOrder());
        Integer[] array = a.toArray(new Integer[0]);
        int sum = 0;
        int i = 1;
        for (; i < (t-1)*3; i+=3) {
            if (a.get(i)<a.get(i+2) && a.get(i+1)==a.get(i+2)){
                int tmp = array[i];
                array[i] = array[i+2];
                array[i+2] = tmp;
            }
            sum += array[i];
        }
        sum += array[i];
        System.out.println(sum);
    }

    //查找公共字符串
    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {// 注意，如果输入是多个测试用例，请通过while循环处理多个测试用例
            String s = in.nextLine();
            StringTokenizer stringTokenizer = new StringTokenizer(s,in.nextLine(),false);
            StringBuilder stringBuilder = new StringBuilder();
            while (stringTokenizer.hasMoreTokens()) {
                stringBuilder.append(stringTokenizer.nextToken());
            }
            System.out.println(stringBuilder);
        }
    }
}
